Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Сравнение СУБД Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 4 5 6 7 8 9 [10] 11 12 13   вперед  Ctrl
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34709


> По какому "делу"? О применимости хэш-таблиц для выполнения группировки и фильтрации
> повторов? Об этом уже всё сказано. О том, что при попадании в хэш-таблицу данные
> упорядочиваются? Вроде бы тоже.

Так ты всё-таки утверждаешь, что "при попадании в хэш-таблицу данные
упорядочиваются"

Ответь пож. кратко, ясно и однозначно. "Да, упорядочиваются", либо "нет, не
упорядочиваются" -- по твоему , естественно мнению.

> Если за два года "профессиональной" работы с хэш-таблицами ты не научился
> держать списки
> коллизий упорядоченными, то стоит подождать ещё лет пять. Может, за это время и
> научишься...

Знаешь ли, существует порядка 100 способов обработки переполнений в
хэш-таблицах, есть такие, которые вообще не используют списки переполнения.

Posted via ActualForum NNTP Server 1.5

20 апр 12, 16:04    [12446811]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 54812

Сергей Арсеньев
В случае упорядоченности крючков да. Но не строгая. Как заметил Bazist нестрогая за
сортировку не катит.

Ага, то есть если номера на куртках уникальны, то это сортировка, а если на двух куртках
случайно окажется один и тот же номер и их повесят на один крючок, то уже нет. Ну тогда
действительно, я был неправ и hash match group сортировку не использует.

Bazist
хештаблица даже и этого не гарантирует если начнет мержить разреженные
страницы памяти.

Вот только не надо тут размахивать деталями Вашей криворукой реализации...

Posted via ActualForum NNTP Server 1.5

20 апр 12, 16:04    [12446813]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
Bazist
Member [заблокирован]

Откуда: Спілкуйся Українською
Сообщений: 8157
Блог
Dimitry Sibiryakov
Вот только не надо тут размахивать деталями Вашей криворукой реализации...


Главное чтобы не быть кривоголовым ... а мою реализацию можно глянуть здесь
20 апр 12, 16:09    [12446852]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 54812

MasterZiv
Хэш-таблица выглядит по-другому:

Вообще-то это то же самое, только ты зачем-то запретил вешать куртки на один крючок. И не
дал себе труд подумать: по какому принципу я написал номера на бирках, пришитых к курткам.

Posted via ActualForum NNTP Server 1.5

20 апр 12, 16:11    [12446864]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
sphinx_mv
Member [заблокирован]

Откуда:
Сообщений: 1672
Bazist
sphinx_mv
Ага... Я уже заценил уровень "профессионализма" человека, для которого нормально для хэш-таблицы "на лету" менять хэш-функцию, не осознавая, что для этого нужно строить СОВЕРШЕННО ДРУГУЮ, НОВУЮ хэш-таблицу, и который считает перестройку хэш-таблицы на пару-тройку десятков миллионов элементов - копеечной задачей...


Посмотри на этот график и поймешь зачем перестраивать таблицу без коллизий
Можешь считать что синий график работает с хешфункцией с коллизиями,
красный уже без при выборе хорошей хешфункции на известном ряде.

Хорошая хэш-функция - это только для "известного ряда"? Ну-ну...
"Известный ряд" сколько раз будете "перехэшировать", пока подберете "хорошую хэш-функцию"? А если в ваш "известный ряд" добавится хотя бы 1 новое значение, Ваша "хорошая" хэш-функция все так же будет гарантировано "хорошей"? А если еще пол-тысячи? А миллион? И все равно гарантировано НЕ будет коллизий?
Смешно... Практически для любой хэш-функции существуют коллизии (сугубо исходя из определения термина). Из этого непосредственно следует, что хэш-функций, никогда не дающих коллизий не существует. Соответственно, Ваш "красный график" - не более чем подгоночная "рекламная" туфта.

А вообще, пара детских вопросов "не-гуманитарию"...
Вы разницу между "созданием таблицы" (оно же "пересоздание" или "перехэширование") и "поиском по таблице" знаете? Или Вы не в курсе, что в переводе с англицкого означает слово "searches"? Ну, а если словарем воспользоваться?
20 апр 12, 16:12    [12446873]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34709


> Вообще-то это то же самое, только ты зачем-то запретил вешать куртки на один
> крючок. И не
> дал себе труд подумать: по какому принципу я написал номера на бирках, пришитых
> к курткам.

Да, согласен.
Но у тебя получилась не модель хэш-таблицы, а просто модель под твой вопрос
по упорядочиванию.


Posted via ActualForum NNTP Server 1.5

20 апр 12, 16:14    [12446889]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
Bazist
Member [заблокирован]

Откуда: Спілкуйся Українською
Сообщений: 8157
Блог
sphinx_mv
Хорошая хэш-функция - это только для "известного ряда"? Ну-ну...
"Известный ряд" сколько раз будете "перехэшировать", пока подберете "хорошую хэш-функцию"? А если в ваш "известный ряд" добавится хотя бы 1 новое значение, Ваша "хорошая" хэш-функция все так же будет гарантировано "хорошей"? А если еще пол-тысячи? А миллион? И все равно гарантировано НЕ будет коллизий?
Смешно... Практически для любой хэш-функции существуют коллизии (сугубо исходя из определения термина). Из этого непосредственно следует, что хэш-функций, никогда не дающих коллизий не существует. Соответственно, Ваш "красный график" - не более чем подгоночная "рекламная" туфта.


Читай внимательней блог.
У меня вообщето не хешфункции, а Trie структуры без коллизий, потому и выборки по дипапазонам есть, потому и скорость поиска ...
20 апр 12, 16:17    [12446900]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 54812

MasterZiv
Но у тебя получилась не модель хэш-таблицы, а просто модель под твой вопрос по упорядочиванию.

Потому что если бы я начал писать многа букаф про то, что номера на бирках это функция
фамилии владельца и т.д. и т.п., то простого ответа бы не получил никогда.

Если Базист жонглирует страницами, это его проблемы. Реализации хэш-таблиц, где массив
указателей на списки ключей выделяется фиксированного размера - гораздо проще, а потому
надёжнее и быстрее.

Posted via ActualForum NNTP Server 1.5

20 апр 12, 16:21    [12446937]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
softwarer
Member

Откуда: 127.0.0.1
Сообщений: 67477
Блог
Bazist
Рядом означает обыкновенную адрессную арифметику и ничего более.
Можно добыть сотый элемент по смещению и это время будет гарантировано более/менее константно

Да ну правда что ли? Разница в шесть порядков теперь называется "более/менее константно"?

Можно добыть элемент по смещению - да. После обращения к некоему элементу скорее всего удастся быстро обратиться к соседним с ним элементам - да. Вот что реально гарантирует массив.
20 апр 12, 16:24    [12446953]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
Bazist
Member [заблокирован]

Откуда: Спілкуйся Українською
Сообщений: 8157
Блог
Dimitry Sibiryakov
Потому что если бы я начал писать многа букаф про то, что номера на бирках это функция
фамилии владельца и т.д. и т.п., то простого ответа бы не получил никогда.
Если Базист жонглирует страницами, это его проблемы. Реализации хэш-таблиц, где массив
указателей на списки ключей выделяется фиксированного размера - гораздо проще, а потому
надёжнее и быстрее.


Ты бы всетаки почитал чо по теме. Что должен гарантировать асоциативный массив. Что не должен.
Пытаешся накласть ограничения на хештаблицы о какомто порядок, которых там никогда не было.
Тотже Judy это 20 тысяч строк мозгодробительного Си кода ориентированого на кеши процессора.
В твоем понимании хештаблица это чтото такое простенькое до опупения. Но какже ты ошибаешся ...
20 апр 12, 16:24    [12446954]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
Bazist
Member [заблокирован]

Откуда: Спілкуйся Українською
Сообщений: 8157
Блог
softwarer
Bazist
Рядом означает обыкновенную адрессную арифметику и ничего более.
Можно добыть сотый элемент по смещению и это время будет гарантировано более/менее константно

Да ну правда что ли? Разница в шесть порядков теперь называется "более/менее константно"?


Эй, а ничего что ты кеши процессора задействовал и теперь пишешь о какихто шести порядках ?
Какое отношение к алгоритмам доступа имеют кеши процессора.
Может хватит втыкать на палец, не ?

softwarer
Можно добыть элемент по смещению - да. После обращения к некоему элементу скорее всего удастся быстро обратиться к соседним с ним элементам - да. Вот что реально гарантирует массив.


О этом и речь.
20 апр 12, 16:27    [12446986]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 54812

Bazist
Ты бы всетаки почитал чо по теме. Что должен гарантировать асоциативный массив. Что не должен.
Пытаешся накласть ограничения на хештаблицы о какомто порядок, которых там никогда не было.

А ты пытаешься притянуть за уши ассоциативные массивы, о которых речи не шло. Прочти уже
первую страницу топика, не ленись.

Posted via ActualForum NNTP Server 1.5

20 апр 12, 17:00    [12447309]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
Bazist
Member [заблокирован]

Откуда: Спілкуйся Українською
Сообщений: 8157
Блог
Dimitry Sibiryakov
Реализации хэш-таблиц, где массив
указателей на списки ключей выделяется фиксированного размера - гораздо проще, а потому
надёжнее и быстрее.


Ну тебя уже тыкнули что те самые списки ключей не будут упорядочеными в твоем простом примере.
А если искать способы увелечения скорости поиска и экономии памяти, то лучше тебе этого не знать,
раз ты еще элементарного не понял.
20 апр 12, 17:06    [12447361]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
Сергей Арсеньев
Member

Откуда:
Сообщений: 4118
Bazist
softwarer
После обращения к некоему элементу скорее всего удастся быстро обратиться к соседним с ним элементам - да. Вот что реально гарантирует массив.
О этом и речь.

И эти люди втирали мне про "почти беременна"...

Да даже нахождение адресов в одном кешлайне ничего не гарантирует. К моменту выполнения второй операции он может уехать на другой процессор и жди его потом обратно.

Dimitry Sibiryakov, просто наивно полагает, что из графика Bazist, следует, что hash работает эффективно, при условии, что элементы исходного множества распределены более-менее равномерно по значениям hash функции. А раз так, то из этого следует, что почти все ячейки будут заняты и поэтому неупорядоченное множество указателей на группы объектов с одинаковым hash ключем ничего не выиграет у упорядоченного (массив) по памяти и сильно проиграет по скорости выборки. Про то, что можно строить заведомо неэффективную hash таблицу ему невдомек.
20 апр 12, 17:09    [12447384]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
Bazist
Member [заблокирован]

Откуда: Спілкуйся Українською
Сообщений: 8157
Блог
Сергей Арсеньев
Bazist
пропущено...
О этом и речь.

И эти люди втирали мне про "почти беременна"...


Кеш не имеет отношение к эффективности алгоритмов в общем случае.
И Кнут какбе тоже несколько томов описывая разные алгоритмы не писал ничего о том что процессор
может чтото закешировать, не правдали ? Так можно и дальше пойти, до конвеера комманд процессора и тд
и из этого можно уже говорить что строки в программе не выполняются гарантировано последовательно, например,
потому что процессор тоже любит коечто оптимизировать ...
20 апр 12, 17:22    [12447496]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 54812

Сергей Арсеньев
Про то, что можно строить заведомо неэффективную hash таблицу ему невдомек.

Вообще-то мне наплевать на эффективность таблицы и скорость поиска. Вся эта дискуссия
началась с того, что я подверг сомнению утверждение "hash match group не использует
сортировку". Поскольку я был убеждён, что любое распределение элементов исходного
множества по последовательным ячейкам и есть сортировка. Собственно, я и до сих пор в этом
убеждён. То, что кучки ключей, набившиеся в одну ячейку, могут быть (в кривой реализации)
не упорядочены - ничего не меняет.

Posted via ActualForum NNTP Server 1.5

20 апр 12, 17:30    [12447572]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 34709


> сортировку". Поскольку я был убеждён, что любое распределение элементов исходного
> множества по последовательным ячейкам и есть сортировка. Собственно, я и до сих
> пор в этом
> убеждён. То, что кучки ключей, набившиеся в одну ячейку, могут быть (в кривой
> реализации)
> не упорядочены - ничего не меняет.

Я предлагаю перейти от дискуссий в практическое русло.
Пусть Дмитрий возмёт и реализует данную задачу на любом из языков,
с использованием хэш-таблицы.

Posted via ActualForum NNTP Server 1.5

20 апр 12, 17:35    [12447618]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
softwarer
Member

Откуда: 127.0.0.1
Сообщений: 67477
Блог
Dimitry Sibiryakov
Поскольку я был убеждён, что любое распределение элементов исходного множества по последовательным ячейкам и есть сортировка.

Ага. (Скучая) Например, "считать файл с диска в оперативку" - это сортировка. Вы в этом убеждены. Ну предложения к модератору я уже озвучивал.
20 апр 12, 17:38    [12447635]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
Bazist
Member [заблокирован]

Откуда: Спілкуйся Українською
Сообщений: 8157
Блог
Dimitry Sibiryakov,

Дима жжот.
Какие нахрен кривые реализации.
Хештаблицы ВСЕГДА генерят коллизии,
майкрасофт хешфункция уже на сто тыщ генерит кучу коллизий. Возьми проверь
есть функция у каждого обьекта гет хеш код
20 апр 12, 17:40    [12447650]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 54812

softwarer
Ага. (Скучая) Например, "считать файл с диска в оперативку" - это сортировка. Вы в этом
убеждены.

Ok, продолжаем разговор... Запрос:
with t as(select 1 as a,2 as b from dual union all
select 1 as a,1 as b from dual union all
select 2 as a,1 as b from dual union all)
select * from t order by a

Вы утверждаете, что этот запрос не делает сортировку, поскольку исходный порядок записей
не изменяется и более того - внутри группы a=1 записи не упорядочены. Я правильно Вас понял?

Posted via ActualForum NNTP Server 1.5

20 апр 12, 17:50    [12447738]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
Сергей Арсеньев
Member

Откуда:
Сообщений: 4118
Bazist
Кеш не имеет отношение к эффективности алгоритмов в общем случае.

Тут я с Вами полностью согласен, правда если заменить "в общем случае" на "теоретически эффективный алгоритм".
Спор напоминаю был про то, что если черный ящик выглядит как утка, это не значит, что внутри там утка, как впрочем и то что ее там нет.
20 апр 12, 17:51    [12447743]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
Bogdanov Andrey
Member

Откуда: Да уже и сам не знаю...
Сообщений: 2203
Dimitry Sibiryakov
исходный порядок записей
А откуда взялся "исходный порядок"?
20 апр 12, 17:54    [12447780]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
Сергей Арсеньев
Member

Откуда:
Сообщений: 4118
Dimitry Sibiryakov
То, что кучки ключей, набившиеся в одну ячейку, могут быть (в кривой реализации) не упорядочены - ничего не меняет.

Упс. Выпал из темы. Т.е. упорядочивать ключи с одинаковым значением кеша?
А на, тоесть зачем их там упорядочивать? Время тратить.
В задаче ТС на 1 проверку приходится ~ 1 вставка.
В этом случае накладные расходы на сортировку съедят эффект от поиска по упорядоченному множеству.
Ну или уж строить дерево и ну его нафиг этот hash.

IMHO конечно полное.
20 апр 12, 17:57    [12447804]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
Bazist
Member [заблокирован]

Откуда: Спілкуйся Українською
Сообщений: 8157
Блог
int collision = 0;
            Dictionary<int, int> list = new Dictionary<int, int>();
            for (int i = 0; i < 10000000; i++)
            {
                try
                {
                    list.Add(i.ToString().GetHashCode(), 0);
                }
                catch (Exception ex)
                {
                    collision++;
                }
            }


Вот, ради интереса.
Свыше 5000 коллизий
10 млн / 5000 = Каждый 2хтысячный элемент на более чем 4х миллиардном элементом попал в коллизию.
Конечно у Майкрософт кривые руки, Дима напишет как надо, чтоб без коллизий и все упорядочено, чо.
20 апр 12, 18:00    [12447828]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
Bazist
Member [заблокирован]

Откуда: Спілкуйся Українською
Сообщений: 8157
Блог
На 25 миллионов элементов, количество коллизий составило 1 миллион 321 тысяча.

Так чо, равномерно хешфункция распределяет элементы по 4х миллиардному диапазону ?
20 апр 12, 18:05    [12447852]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 4 5 6 7 8 9 [10] 11 12 13   вперед  Ctrl
Все форумы / Сравнение СУБД Ответить