ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Сравнение СУБД [игнор отключен] [закрыт для гостей] / СУБД для временного хранения данных из бинарного файла (под Delphi).
25 сообщений из 311, страница 10 из 13
  10  все
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763400
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
> По какому "делу"? О применимости хэш-таблиц для выполнения группировки и фильтрации
> повторов? Об этом уже всё сказано. О том, что при попадании в хэш-таблицу данные
> упорядочиваются? Вроде бы тоже.

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

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

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

Знаешь ли, существует порядка 100 способов обработки переполнений в
хэш-таблицах, есть такие, которые вообще не используют списки переполнения.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
20.04.2012, 16:04
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763402
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Сергей АрсеньевВ случае упорядоченности крючков да. Но не строгая. Как заметил Bazist нестрогая за
сортировку не катит.

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

Bazistхештаблица даже и этого не гарантирует если начнет мержить разреженные
страницы памяти.
Вот только не надо тут размахивать деталями Вашей криворукой реализации...
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
20.04.2012, 16:04
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763421
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
Dimitry SibiryakovВот только не надо тут размахивать деталями Вашей криворукой реализации...


Главное чтобы не быть кривоголовым ... а мою реализацию можно глянуть здесь
...
Рейтинг: 0 / 0
20.04.2012, 16:09
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763428
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
MasterZivХэш-таблица выглядит по-другому:

Вообще-то это то же самое, только ты зачем-то запретил вешать куртки на один крючок. И не
дал себе труд подумать: по какому принципу я написал номера на бирках, пришитых к курткам.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
20.04.2012, 16:11
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763432
sphinx_mv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
sphinx_mv
Участник
Bazistsphinx_mvАга... Я уже заценил уровень "профессионализма" человека, для которого нормально для хэш-таблицы "на лету" менять хэш-функцию, не осознавая, что для этого нужно строить СОВЕРШЕННО ДРУГУЮ, НОВУЮ хэш-таблицу, и который считает перестройку хэш-таблицы на пару-тройку десятков миллионов элементов - копеечной задачей...


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

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

А вообще, пара детских вопросов "не-гуманитарию"...
Вы разницу между "созданием таблицы" (оно же "пересоздание" или "перехэширование") и "поиском по таблице" знаете? Или Вы не в курсе, что в переводе с англицкого означает слово "searches"? Ну, а если словарем воспользоваться?
...
Рейтинг: 0 / 0
20.04.2012, 16:12
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763444
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
> Вообще-то это то же самое, только ты зачем-то запретил вешать куртки на один
> крючок. И не
> дал себе труд подумать: по какому принципу я написал номера на бирках, пришитых
> к курткам.

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


Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
20.04.2012, 16:14
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763450
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
sphinx_mvХорошая хэш-функция - это только для "известного ряда"? Ну-ну...
"Известный ряд" сколько раз будете "перехэшировать", пока подберете "хорошую хэш-функцию"? А если в ваш "известный ряд" добавится хотя бы 1 новое значение, Ваша "хорошая" хэш-функция все так же будет гарантировано "хорошей"? А если еще пол-тысячи? А миллион? И все равно гарантировано НЕ будет коллизий?
Смешно... Практически для любой хэш-функции существуют коллизии (сугубо исходя из определения термина). Из этого непосредственно следует, что хэш-функций, никогда не дающих коллизий не существует. Соответственно, Ваш "красный график" - не более чем подгоночная "рекламная" туфта.


Читай внимательней блог.
У меня вообщето не хешфункции, а Trie структуры без коллизий, потому и выборки по дипапазонам есть, потому и скорость поиска ...
...
Рейтинг: 0 / 0
20.04.2012, 16:17
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763465
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
MasterZivНо у тебя получилась не модель хэш-таблицы, а просто модель под твой вопрос по упорядочиванию.

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

Если Базист жонглирует страницами, это его проблемы. Реализации хэш-таблиц, где массив
указателей на списки ключей выделяется фиксированного размера - гораздо проще, а потому
надёжнее и быстрее.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
20.04.2012, 16:21
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763474
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
BazistРядом означает обыкновенную адрессную арифметику и ничего более.
Можно добыть сотый элемент по смещению и это время будет гарантировано более/менее константно
Да ну правда что ли? Разница в шесть порядков теперь называется "более/менее константно"?

Можно добыть элемент по смещению - да. После обращения к некоему элементу скорее всего удастся быстро обратиться к соседним с ним элементам - да. Вот что реально гарантирует массив.
...
Рейтинг: 0 / 0
20.04.2012, 16:24
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763475
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
Dimitry SibiryakovПотому что если бы я начал писать многа букаф про то, что номера на бирках это функция
фамилии владельца и т.д. и т.п., то простого ответа бы не получил никогда.
Если Базист жонглирует страницами, это его проблемы. Реализации хэш-таблиц, где массив
указателей на списки ключей выделяется фиксированного размера - гораздо проще, а потому
надёжнее и быстрее.


Ты бы всетаки почитал чо по теме. Что должен гарантировать асоциативный массив. Что не должен.
Пытаешся накласть ограничения на хештаблицы о какомто порядок, которых там никогда не было.
Тотже Judy это 20 тысяч строк мозгодробительного Си кода ориентированого на кеши процессора.
В твоем понимании хештаблица это чтото такое простенькое до опупения. Но какже ты ошибаешся ...
...
Рейтинг: 0 / 0
20.04.2012, 16:24
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763490
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
softwarerBazistРядом означает обыкновенную адрессную арифметику и ничего более.
Можно добыть сотый элемент по смещению и это время будет гарантировано более/менее константно
Да ну правда что ли? Разница в шесть порядков теперь называется "более/менее константно"?


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

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

О этом и речь.
...
Рейтинг: 0 / 0
20.04.2012, 16:27
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763597
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
BazistТы бы всетаки почитал чо по теме. Что должен гарантировать асоциативный массив. Что не должен.
Пытаешся накласть ограничения на хештаблицы о какомто порядок, которых там никогда не было.

А ты пытаешься притянуть за уши ассоциативные массивы, о которых речи не шло. Прочти уже
первую страницу топика, не ленись.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
20.04.2012, 17:00
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763614
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
Dimitry SibiryakovРеализации хэш-таблиц, где массив
указателей на списки ключей выделяется фиксированного размера - гораздо проще, а потому
надёжнее и быстрее.


Ну тебя уже тыкнули что те самые списки ключей не будут упорядочеными в твоем простом примере.
А если искать способы увелечения скорости поиска и экономии памяти, то лучше тебе этого не знать,
раз ты еще элементарного не понял.
...
Рейтинг: 0 / 0
20.04.2012, 17:06
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763619
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
Bazistsoftwarer После обращения к некоему элементу скорее всего удастся быстро обратиться к соседним с ним элементам - да. Вот что реально гарантирует массив.О этом и речь.
И эти люди втирали мне про "почти беременна"...

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

Dimitry Sibiryakov, просто наивно полагает, что из графика Bazist, следует, что hash работает эффективно, при условии, что элементы исходного множества распределены более-менее равномерно по значениям hash функции. А раз так, то из этого следует, что почти все ячейки будут заняты и поэтому неупорядоченное множество указателей на группы объектов с одинаковым hash ключем ничего не выиграет у упорядоченного (массив) по памяти и сильно проиграет по скорости выборки. Про то, что можно строить заведомо неэффективную hash таблицу ему невдомек.
...
Рейтинг: 0 / 0
20.04.2012, 17:09
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763651
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
Сергей АрсеньевBazistпропущено...
О этом и речь.
И эти люди втирали мне про "почти беременна"...


Кеш не имеет отношение к эффективности алгоритмов в общем случае.
И Кнут какбе тоже несколько томов описывая разные алгоритмы не писал ничего о том что процессор
может чтото закешировать, не правдали ? Так можно и дальше пойти, до конвеера комманд процессора и тд
и из этого можно уже говорить что строки в программе не выполняются гарантировано последовательно, например,
потому что процессор тоже любит коечто оптимизировать ...
...
Рейтинг: 0 / 0
20.04.2012, 17:22
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763676
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Сергей АрсеньевПро то, что можно строить заведомо неэффективную hash таблицу ему невдомек.

Вообще-то мне наплевать на эффективность таблицы и скорость поиска. Вся эта дискуссия
началась с того, что я подверг сомнению утверждение "hash match group не использует
сортировку". Поскольку я был убеждён, что любое распределение элементов исходного
множества по последовательным ячейкам и есть сортировка. Собственно, я и до сих пор в этом
убеждён. То, что кучки ключей, набившиеся в одну ячейку, могут быть (в кривой реализации)
не упорядочены - ничего не меняет.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
20.04.2012, 17:30
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763687
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
> сортировку". Поскольку я был убеждён, что любое распределение элементов исходного
> множества по последовательным ячейкам и есть сортировка. Собственно, я и до сих
> пор в этом
> убеждён. То, что кучки ключей, набившиеся в одну ячейку, могут быть (в кривой
> реализации)
> не упорядочены - ничего не меняет.

Я предлагаю перейти от дискуссий в практическое русло.
Пусть Дмитрий возмёт и реализует данную задачу на любом из языков,
с использованием хэш-таблицы.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
20.04.2012, 17:35
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763690
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
Dimitry SibiryakovПоскольку я был убеждён, что любое распределение элементов исходного множества по последовательным ячейкам и есть сортировка.
Ага. (Скучая) Например, "считать файл с диска в оперативку" - это сортировка. Вы в этом убеждены. Ну предложения к модератору я уже озвучивал.
...
Рейтинг: 0 / 0
20.04.2012, 17:38
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763694
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
Dimitry Sibiryakov,

Дима жжот.
Какие нахрен кривые реализации.
Хештаблицы ВСЕГДА генерят коллизии,
майкрасофт хешфункция уже на сто тыщ генерит кучу коллизий. Возьми проверь
есть функция у каждого обьекта гет хеш код
...
Рейтинг: 0 / 0
20.04.2012, 17:40
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763720
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
softwarerАга. (Скучая) Например, "считать файл с диска в оперативку" - это сортировка. Вы в этом
убеждены.

Ok, продолжаем разговор... Запрос:
Код: sql
1.
2.
3.
4.
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
...
Рейтинг: 0 / 0
20.04.2012, 17:50
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763722
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
BazistКеш не имеет отношение к эффективности алгоритмов в общем случае.
Тут я с Вами полностью согласен, правда если заменить "в общем случае" на "теоретически эффективный алгоритм".
Спор напоминаю был про то, что если черный ящик выглядит как утка, это не значит, что внутри там утка, как впрочем и то что ее там нет.
...
Рейтинг: 0 / 0
20.04.2012, 17:51
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763735
Bogdanov Andrey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bogdanov Andrey
Участник
Dimitry Sibiryakovисходный порядок записей А откуда взялся "исходный порядок"?
...
Рейтинг: 0 / 0
20.04.2012, 17:54
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763741
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
Dimitry SibiryakovТо, что кучки ключей, набившиеся в одну ячейку, могут быть (в кривой реализации) не упорядочены - ничего не меняет.
Упс. Выпал из темы. Т.е. упорядочивать ключи с одинаковым значением кеша?
А на, тоесть зачем их там упорядочивать? Время тратить.
В задаче ТС на 1 проверку приходится ~ 1 вставка.
В этом случае накладные расходы на сортировку съедят эффект от поиска по упорядоченному множеству.
Ну или уж строить дерево и ну его нафиг этот hash.

IMHO конечно полное.
...
Рейтинг: 0 / 0
20.04.2012, 17:57
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763752
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
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х миллиардном элементом попал в коллизию.
Конечно у Майкрософт кривые руки, Дима напишет как надо, чтоб без коллизий и все упорядочено, чо.
...
Рейтинг: 0 / 0
20.04.2012, 18:00
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763760
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
На 25 миллионов элементов, количество коллизий составило 1 миллион 321 тысяча.

Так чо, равномерно хешфункция распределяет элементы по 4х миллиардному диапазону ?
...
Рейтинг: 0 / 0
20.04.2012, 18:05
| Ответить | Цитировать | Написать  
25 сообщений из 311, страница 10 из 13
  10  все
Форумы / Сравнение СУБД [игнор отключен] [закрыт для гостей] / СУБД для временного хранения данных из бинарного файла (под Delphi).
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=35&msg=37763450&tid=1552562]:
 0ms
get settings:
 10ms
get forum list:
 14ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 34ms
get topic data:
 11ms
get forum data:
 2ms
get page messages:
 61ms
get tp. blocked users:
 1ms
others: 240ms
total:  381ms
созд. / загр.: 381ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]