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

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

> Дословно:
> 1) Данные помещаются в хэш-таблицу.
> 2) Значение хэша служит индексом в этой таблице.
> 3) Таблицы упорядочена по возрастанию индекса.
>
> i и j в данном случае - индексы элементов хэш-таблицы. То есть сами значения хэшей.

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

Я извиняюсь, но...

У меня сложилось подозрение, что Вы сильно зауживаете понятие и использование хэш-функций и хэш-таблиц.
По сути UPPER, LOWER, не говоря уже о SOUNDEX, тоже могут считаться хэш-функциями, а индексы в БД - хэш-таблицами.
Соответствеенно, и сама хэш-функция известна, и доступ к ее результату тоже имеется.
И у Вас не совсем правильный вывод о том, что значение хэш-функции "меняется со временем": на самом деле хеширование выполняется с конкатенацией метки времени и оригинальным значением - потому и создается такое впечатление...

При необходимости часто делать выборки из больших таблиц по точному совпадению в полях больших размеров (например, текстовых идентификаторов), для ускорения поиска и уменьшения места, занимаемого индексами физической таблицы, можно использовать индекс по значению хэш-функции для этого конкретного поля. Соотвественно, в условии выборки используется уже не значение поля, а значение хэш-функции от кроиерия выборки по этому полю. Естественно, что не следует забывать про возможные коллизии при этом.
20 апр 12, 11:32    [12444280]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
MasterZiv
Member

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

On 04/20/2012 12:31 PM, Dimitry Sibiryakov wrote:

> MasterZiv
> Индексом в хэш-таблице служит ключ данных
> А адресного пространства хватит на данные с ключом размером в пару килобайт?..

Браво, Дмитрий, пиши ещё!

Posted via ActualForum NNTP Server 1.5

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

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


> У меня сложилось подозрение, что Вы сильно зауживаете понятие и использование
> хэш-функций и хэш-таблиц.
> По сути UPPER, LOWER, не говоря уже о SOUNDEX, тоже могут считаться
> хэш-функциями, а индексы в БД - хэш-таблицами.

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


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

Чё? Я имел в виду, что если ты возмёщь одну современную хэш-таблицу в
произвольном языке программирования и начнёшь её заполнять, сначала
для хэширования будет использоваться одна хэш-функция, потом, с ростом
таблицы, возможно, она будет заменена на другую (прозрачно для пользователя,
естестенно).

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

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

Posted via ActualForum NNTP Server 1.5

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

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

MasterZiv
потом, с ростом таблицы, возможно, она будет заменена на другую

Гениально! Пеши есчо!

Posted via ActualForum NNTP Server 1.5

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

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

Гениально! Пеши есчо!


В том то и дело, что это не он гениален, это ты слегка туповат.
Модератор: в следующий раз за переход на личности буду банить

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

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

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

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

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

Posted via ActualForum NNTP Server 1.5

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

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


> Не поверю. Продемонстрируй, что происходит, когда в таблицу уже загнали 100500
> записей,
> она разрослась и - опа! - решила поменять хэш-функцию.

Перехэширование.

Posted via ActualForum NNTP Server 1.5

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

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

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


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

Откуда: Спілкуйся Українською
Сообщений: 8157
Блог
О сколько Диме открытий чудных,
готовит просвещенья век (с)
20 апр 12, 13:10    [12445158]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
Сергей Арсеньев
Member

Откуда:
Сообщений: 4118
Bazist
При большом количестве элементов растет количество коллизий и хештаблица выраждается в унылый тормоз если хешфункция подобрана неудачно для этого ряда.

Поэтому в индексах чаще и используют деревья, сруктура которых по сути и является динамической hash функцией. Но естественно требует дополнительных затрат на постоянное обновление.

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

Откуда:
Сообщений: 4118
Bazist
О сколько Диме открытий чудных,
готовит просвещенья век (с)

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

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

MasterZiv
Перехэширование.

Подробнее, пожалуйста. Что Вы зовёте "перехешированием"?

Posted via ActualForum NNTP Server 1.5

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

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


> Поэтому в индексах чаще и используют деревья, сруктура которых по сути и
> является динамической hash функцией. Но естественно требует дополнительных
> затрат на постоянное обновление.

Это твои фантазии.

> P.S. Я понимаю, что за обсуждение действий модераторов тут банят, чуть ли не
> пожизненно, но Дмитрий всего лишь процитировал то, что ему написали несколькими
> страницами ранее.

Кто его банит-то ? Без него скучно будет. :-)



Posted via ActualForum NNTP Server 1.5

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

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

> У меня сложилось подозрение, что Вы сильно зауживаете понятие и использование
> хэш-функций и хэш-таблиц.
> По сути UPPER, LOWER, не говоря уже о SOUNDEX, тоже могут считаться
> хэш-функциями, а индексы в БД - хэш-таблицами.

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

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

Чё? Я имел в виду, что если ты возмёщь одну современную хэш-таблицу в
произвольном языке программирования и начнёшь её заполнять, сначала
для хэширования будет использоваться одна хэш-функция, потом, с ростом
таблицы, возможно, она будет заменена на другую (прозрачно для пользователя,
естестенно).

Извините, но это - БРЕД!

Я допускаю, что некоторые библиотеки могут позволять выбор разных хэш-функции для реализации хэш-таблиц.
Но вот то, что в ран-тайме в течение всего периода жизни экземпяра хэш-таблицы вне зависимости от степени ее роста хэш-функция НЕ меняется - это, как бы, аксиома... Любая попытка замены хэширующей функции "на лету" приводит к эскалации коллизий и некорректности функционирования ЛЮБОГО алгоритма, работающего с этой хэш-таблицей.
MasterZiv
> При необходимости часто делать выборки из больших таблиц по точному совпадению в
> полях больших размеров (например, текстовых идентификаторов), для ускорения
> поиска и уменьшения места, занимаемого индексами физической таблицы, можно
> использовать индекс по значению хэш-функции для этого конкретного поля.
> Соотвественно, в условии выборки используется уже не значение поля, а значение
> хэш-функции от кроиерия выборки по этому полю. Естественно, что не следует
> забывать про возможные коллизии при этом.

Большего идиотизма трудно придумать.
-- можно просто не использовать длинные текстовые поля в индексах.

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

Вы неверно понимаете сжатие ключей индексов, которые могут выполнять некоторые промышленные СУБД.
Исключения из ключа индекса незначащей части не дает существеной экономии места, когда ключ заполнен "в-среднем" процентов на 90-95 для каждой записи... При длине ключа байт хотя бы на 100... С учетом "сжатия"...
20 апр 12, 13:23    [12445279]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
Bazist
Member [заблокирован]

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

А теперь в кратце, Вы тоже считаете, что хеш таблица не упорядоченна, потому что ее порядок не соответствует некому мифическому ключу?


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

Откуда: 127.0.0.1
Сообщений: 67393
Блог
sphinx_mv
По сути UPPER, LOWER, не говоря уже о SOUNDEX, тоже могут считаться хэш-функциями,

Только очень теоретически. Они практически неприменимы в тех ситуациях, в которых мы хотим применять хэш-функции.

sphinx_mv
а индексы в БД - хэш-таблицами.

Совсем нет. Примерно с тем же успехом можно сказать "full table scan можно считать доступом по индексу" - для того, чтобы это стало верным, нужно подняться на столь высокую ступень абстракции, что вообще теряется какой-либо смысл.

sphinx_mv
Соответствеенно, и сама хэш-функция известна, и доступ к ее результату тоже имеется.

Пусть имеется. Я не зря писал в своих требованиях про возможность замены хэш-функции без потери работоспособности решения и стабильности результата.
20 апр 12, 13:24    [12445293]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
Сергей Арсеньев
Member

Откуда:
Сообщений: 4118
MasterZiv
Кто его банит-то ? Без него скучно будет. :-)

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

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


> А теперь в кратце, Вы тоже считаете, что хеш таблица не упорядоченна, потому что
> ее порядок не соответствует некому мифическому ключу?

По какому критерию она упорядочена ?
Расскажи, а мы рассмотрим.

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

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

Если ты тоже предполагаешь, что хэш-таблица что-то сортирует, то расскажи,
что это.

Почему вопрос принципиален -- самая быстрая сортировка это
O( N log N )

в то время как производительность хэш-таблицы
O( 1 )

Если бы хэш-таблица что-то сортировала бы, она не могла бы добиться
производительности в O( 1 ).

Posted via ActualForum NNTP Server 1.5

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

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

Dimitry Sibiryakov
Что происходит?

Bazist
Да, так и есть.

Это мне одному напоминает анекдот про блондинку?..

Bazist
Что мне с "упорядочиваний" хештаблицы если я не могу вытянуть элементы в сортированом
порядке по ключу, не могу вытягивать элементы по диапазону ключей и так далее ?

Но вы можете за один проход вытянуть список неповторяющихся элементов. Этого достаточно
для работы предикатов DISTINCT и GROUP BY.

Posted via ActualForum NNTP Server 1.5

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

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

On 04/20/2012 02:21 PM, Dimitry Sibiryakov wrote:

> MasterZiv
> Перехэширование.

> Подробнее, пожалуйста. Что Вы зовёте "перехешированием"?

Вот смотри, ты вроде бы "поугас". Мы даём тебе "перехэширование".
Ты снова начинаешь постить всякую фигню, и все пруца.
Вот, это и есть "эффект перехэширования".

Posted via ActualForum NNTP Server 1.5

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

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


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

Уж могу тебя заверить. В хэш-таблицах я профессионал.

> Извините, но это - БРЕД!

Всё, иди читай чтонибудь уже.

Posted via ActualForum NNTP Server 1.5

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

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


> Не во всех местных форумах так либеральны.

Я замолвлю словечко, если что. :-)
(серьёзно): Да нет, за что ж его банить, он ничего не нарушал.

Posted via ActualForum NNTP Server 1.5

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

Откуда:
Сообщений: 4118
Bazist
Давай тыкнем пальцем на хаос и скажем что он особым образом упорядочен.

Это не возможно. Если он упорядочен, то он не хаос по определению.

Bazist
Что мне с "упорядочиваний" хештаблицы если я не могу вытянуть элементы в сортированом порядке по ключу, не могу вытягивать элементы по диапазону ключей и так далее?

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

Собственно, правильного ответа, почему создание хеш таблицы не является сортировкой я лично дал здесь - 12440698.
20 апр 12, 13:35    [12445382]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
Сергей Арсеньев
Member

Откуда:
Сообщений: 4118
Сергей Арсеньев,

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

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

MasterZiv
самая быстрая сортировка это
O( N log N )

Что я там говорил про ограничение понятия "сортировка" обменными алгоритмами?.. Правильно,
что кому-то пора перечитать Кнута.

MasterZiv
Вот смотри, ты вроде бы "поугас". Мы даём тебе "перехэширование".
Ты снова начинаешь постить всякую фигню, и все пруца.
Вот, это и есть "эффект перехэширования".

Т.е. создаётся новый массив и все 100500 записей из старого массива переносятся в новый.
Пользователь может пока покурить.

Posted via ActualForum NNTP Server 1.5

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