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

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

Сергей Арсеньев
Собственно, правильного ответа, почему создание хеш таблицы не является сортировкой я
лично дал здесь

Ок, деградируем дискуссию до уровня начальной школы:

Задача:
Мальчик Петя дежурит по раздевалке, в которой есть вешалка с крючками, подписанными от 1
до 100. На полу валяется куча курток, на которых пришиты бирки с номерами. Мальчик Петя
берёт куртки из кучи и вешает на крючки с соответствующими номерами.

Вопросы:
Были ли упорядочены куртки в куче?
Упорядочены ли куртки, висящие на крюках?
Можно ли утверждать, что мальчик Петя их отсортировал?
Отсортированы ли они по фамилиям владельцев?

Posted via ActualForum NNTP Server 1.5

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

Откуда: Спілкуйся Українською
Сообщений: 8157
Блог
Dimitry Sibiryakov
Но вы можете за один проход вытянуть список неповторяющихся элементов. Этого достаточно
для работы предикатов DISTINCT и GROUP BY.


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

Откуда:
Сообщений: 4118
Dimitry Sibiryakov
Ок, деградируем дискуссию до уровня начальной школы:

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

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

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

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

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

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

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

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

Откуда:
Сообщений: 4118
Поясняю на Вашем примере
Dimitry Sibiryakov
есть вешалка с крючками, подписанными от 1 до 100.

Крючки не отсортированы, Хотя и упорядоченны.

Dimitry Sibiryakov
На полу валяется куча курток, на которых пришиты бирки с номерами.

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

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


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

Картинка с другого сайта.

+

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

Откуда:
Сообщений: 4118
Люди предлагаю поднапрячься, еще чуть-чуть и мы переплюнем "Чем MS SQL Server хуже Oracle Database?"
20 апр 12, 14:15    [12445727]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
Dimitry Sibiryakov
Member

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

Сергей Арсеньев
Обычно hash таблицу с указателями на подмножества однохешевых строк создают изначально
упорядоченной и никто ее специально не сортирует.

А теперь перечитываем вопросы. Написано там "были ли упорядочены крючки на вешалке?" Нет.
Сортировал ли Петя крючки на вешалке? Опять таки нет.

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

Posted via ActualForum NNTP Server 1.5

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

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

Откуда: Спілкуйся Українською
Сообщений: 8157
Блог
Bazist
Dimitry Sibiryakov
Но вы можете за один проход вытянуть список неповторяющихся элементов. Этого достаточно
для работы предикатов DISTINCT и GROUP BY.


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


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

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

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

Ага, я понял: ты разделяешь "создание хэш-таблицы" и "заполнение хэш-таблицы данными". Я,
когда писал "создание" всегда имел ввиду именно "заполнение", поскольку объявление массива
указателей и выделение памяти под него мне называть "процессом создания" как-то непривычно...

Ну так ответь одним словом: сортируются куртки при развешивании по крючкам или нет? Просто
"да" или "нет".

Posted via ActualForum NNTP Server 1.5

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

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

Bazist
Дима, можно засчитывать слив ?

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

Posted via ActualForum NNTP Server 1.5

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

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

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


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

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

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

Bazist
Ну а по делу есть чо ?

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

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

Posted via ActualForum NNTP Server 1.5

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

Откуда:
Сообщений: 4118
Dimitry Sibiryakov
Плевать, что массив в хэш-таблице изначально упорядочен, речь идёт о куртках, то бишь
данных на входе.

Дело в том, что пусть A{ai} исходное множество. На выходе получаем
B{Cj}, где Сj это множество {ai} (подмножество A).

Вопрос - является ли ai членом множества B?
20 апр 12, 14:37    [12445951]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
Bazist
Member [заблокирован]

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

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


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

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


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

Откуда:
Сообщений: 4118
Bazist
Какой именно порядок может гарантировать хештаблица.

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

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

Сергей Арсеньев
Дело в том, что пусть A{ai} исходное множество. На выходе получаем
B{Cj}, где Сj это множество {ai} (подмножество A).

Вопрос - является ли ai членом множества B?

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

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

Т.е. то, что я в этом топике уже полдюжины раз сказал "по неубыванию хэша" тебя не
убедило?.. Хорошо, я не гордый, повторю ещё раз: хэш-таблица гарантирует расположение
элементов множества в порядке неубывания хэша ключей элементов этого множества.

Posted via ActualForum NNTP Server 1.5

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

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

Гм. У вас ссылки на множества коллизий организованы массивом или произвольным списком?


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

Откуда:
Сообщений: 4118
Dimitry Sibiryakov
Не понял. Переведи.
В той математике, которую я помню, множество обозначается одной буквой, а фигурных скобок вовсе не используется.

A={ai} - А это множество элементов ai
20 апр 12, 14:56    [12446171]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
Bazist
Member [заблокирован]

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



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

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

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

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

Где выделенное слово?


Тоесть у вас получается немножко беременна

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

Откуда:
Сообщений: 4118
Bazist
Нет дружок, элементы или упорядочены или нет, третьего не дано.

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