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

Предполагается такой план работы:
1. Чтение и одновременная запись из бинарника в БД;
2. Запрос на поиск дублирующихся данных (совпадение нескольких полей у разных записей);
3. Произведение выбранного действия (либо просто ответ да\нет, сколько и т.п.);
4. Вывод инфы из БД в бинарник (опционально);
5. Очистка временной БД;

Соответственно ищется БД с достаточно большой скоростью записи и поиска дублирующихся значений. Как дополнительно - желательно встраиваемая в исполняемый файл, дабы не смущать пользователей лишними файлами (но это не обязательно).

Ну и желательно (но совсем не обязательно) - описание того как вообще с ней работать (запросы и т.п.).

Кто чего посоветует???
...
Рейтинг: 0 / 0
17.04.2012, 22:52
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37758158
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
Посоветуем не забивать гвозди микроскопом и решить задачу тупо и просто (а заодно намного более эффективно).
...
Рейтинг: 0 / 0
17.04.2012, 22:59
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37758160
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
softwarerрешить задачу тупо и просто

Ну что ты, он же Кнута не читал, ему для сортировки и поиска дубликатов позарез СУБД
нужна... FvMAS - то, что ему нужно. Как раз на Дельфи...
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
17.04.2012, 23:02
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37758164
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
Dimitry SibiryakovНу что ты, он же Кнута не читал, ему для сортировки и поиска дубликатов позарез СУБД
нужна... Читавший Кнута вряд ли станет решать эту задачу сортировкой.. Разве что если при записи обратно в бинарник она всё равно нужна.
...
Рейтинг: 0 / 0
17.04.2012, 23:07
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37758166
Freimaks
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Freimaks
Гость
Понял, что надо почитать Кнута... да его я не читал, скрывать не буду...
...
Рейтинг: 0 / 0
17.04.2012, 23:11
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37758168
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
softwarerЧитавший Кнута вряд ли станет решать эту задачу сортировкой..

Э? А как?..
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
17.04.2012, 23:12
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37758180
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
Freimaks
Кто чего посоветует???

Я так думаю нужно поискать компонет реализующий set , multiset, map, multimap для делфи.
...
Рейтинг: 0 / 0
17.04.2012, 23:23
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37758190
без сортировки
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
без сортировки
Гость
Dimitry SibiryakovsoftwarerЧитавший Кнута вряд ли станет решать эту задачу сортировкой..

Э? А как?..

Так же как это делают все современные СУБД, без сортировки.
...
Рейтинг: 0 / 0
17.04.2012, 23:36
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37758206
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
без сортировкиТак же как это делают все современные СУБД, без сортировки.

А конкретнее? Как это делает Оракул, например?
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
17.04.2012, 23:58
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37758211
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
> Понял, что надо почитать Кнута... да его я не читал, скрывать не буду...

Смотри, пока всего не прочитаешь -- и не думай двигаться дальше !
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
18.04.2012, 00:03
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37758234
hash match group by
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hash match group by
Гость
Dimitry Sibiryakovбез сортировкиТак же как это делают все современные СУБД, без сортировки.

А конкретнее? Как это делает Оракул, например?

hash match group by
...
Рейтинг: 0 / 0
18.04.2012, 00:57
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37758275
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
hash match group byhash match group by
А сортировка по хэшу, конечно же, сортировкой не является. Ню-ню...
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
18.04.2012, 02:07
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37758279
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
"Сортировка по хэшу" - это в анналы. "Автор, пеши исчо" (ц)
...
Рейтинг: 0 / 0
18.04.2012, 02:17
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37758281
hash match group by
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hash match group by
Гость
Dimitry Sibiryakovhash match group byhash match group by
А сортировка по хэшу, конечно же, сортировкой не является. Ню-ню...

А как это происходит и в чем преимущество данной сортировки в двух словах расскажите.
...
Рейтинг: 0 / 0
18.04.2012, 02:22
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37758318
Фотография kdv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kdv
Участник
hash match group byА как это происходит и в чем преимущество данной сортировки в двух словах расскажите.
программист должен изучить все виды сортировок, и потом их применять по месту, как из "словаря". Например, я помню, что есть много разных сортировок, и чем они отличаются, но я не помню, как эти сортировки реализованы (код). Но мне это нафиг не надо - открыл любой справочник по программированию, и посмотрел.
...
Рейтинг: 0 / 0
18.04.2012, 04:05
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37758459
Sergey Orlov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sergey Orlov
Участник
Любая NO-SQL база...
...
Рейтинг: 0 / 0
18.04.2012, 09:50
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37758486
Vladimir Baskakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Vladimir Baskakov
Участник
Freimaks 2. Запрос на поиск дублирующихся данных (совпадение нескольких полей у разных записей);
softwarerПосоветуем не забивать гвозди микроскопом
ну - если наборы полей разные? почему бы и не БД? Firebird встроенный или Sqlite как мне думается могут подойти.
Изучать Кнута конечно полезно, и сортировки знать надо... Но на готовом движке получить желаемый результат проще, трудозатраты меньше, гибкость приемлимая - а скорость работы программы так ли сильно пострадает?
...
Рейтинг: 0 / 0
18.04.2012, 10:01
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37758619
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
On 04/18/2012 03:07 AM, Dimitry Sibiryakov wrote:

> А сортировка по хэшу, конечно же, сортировкой не является. Ню-ню...

Хэш не сортирует. Хэш группирует как максимум.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
18.04.2012, 11:04
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37758624
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
Vladimir Baskakovну - если наборы полей разные? почему бы и не БД?
Потому что писать загрузку в БД, выгрузку из БД и решать попутные проблемы будет дольше, чем идти прямым путём, и даст куда худший результат.

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

Vladimir Baskakov - а скорость работы программы так ли сильно пострадает?
Весьма и весьма. Нормальная программа для этой задачи представляет собой трубу ввод-вывод с фильтром и эффективно параллелится, а с БД придётся сначала всё загрузить, потом обрабатывать (и небось сортировкой - судя по Дмитрию ФБ другого не умеет, лайт тоже вряд ли кто оптимизировал), потом выгружать, и всё это с приседаниями и ненужными проблемами (скажем, конвертацией чисел в какой-нибудь BCD-шный decimal).
...
Рейтинг: 0 / 0
18.04.2012, 11:06
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37758627
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
P.S. Не говоря уже о том, что БД будет склонна ещё раз записать эти данные на диск, особенно если они не будут влезать в объём оперативки.
...
Рейтинг: 0 / 0
18.04.2012, 11:07
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37758678
Vladimir Baskakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Vladimir Baskakov
Участник
я боюсь, что если не хватит объема оперативки - своп тоже что-то запишет на диск))))). В индексах БД те-же деревья..... которые используются для удаления дублей из множеств? если совсем грубо? анализ содержимого реляционной БД - запросы с груп-баями. насколько они разнообразны, и насколько просто писать их аналог над самопальными структурами данных? Будет ли эта самопальщина в итоге быстрее?

Стебелек дарит надежду!
http://www.sql.ru/forum/actualthread.aspx?tid=863510 - фтристарас.... Я ничего не путаю?
...
Рейтинг: 0 / 0
18.04.2012, 11:27
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37758697
Vladimir Baskakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Vladimir Baskakov
Участник
ну и уж если самому....
то может книжка подскажет....

Бакнелл. "Фундаментальные алгоритмы с структуры данных в Delphi"
...
Рейтинг: 0 / 0
18.04.2012, 11:32
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37758866
Freimaks
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Freimaks
Гость
Я уже совсем запутался.
Запихал все в динамический массив, по крайней мере все влазит в оперативу, и теперь надо это все обрабатывать.
Если с субд мне было более ли менее ясно что и как - есть физическая база, к которой я делаю запрос, то с массивом в оперативке мне вообще ничего не ясно. Я к сожалению просто любитель в программировании.
Массив делаю так:
1. Объявляю тип record, в котором описываю свои данные
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
type
TBinPoints_time = packed record //стандартный bin без цвета
PointCoordX: integer;
PointCoordY: integer;
PointCoordZ: integer;
PointCode: byte;
PointEcho: byte;
PointFlag: byte;
PointMark: byte;
PointLine: word;
PointInt:  word;
PointTime: cardinal;
end;
2. Объявляю переменные каждой записи и массива записей (может и не прав, но другого не пришло)
Код: plaintext
1.
2.
3.
4.
5.
var
  Form1: TForm1;
  i:integer;
  PTime:TBinPoints_time;
  PTimeArray:array of TBinPoints_time;
3. Ну и далее процедура чтения
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
procedure ReadBinPointsWithRecord(const FileName: String; Output: TStrings);
begin
i:=0;
with TBinaryReader.Create(FileName) do
try
BaseStream.Read(BinHeader, SizeOf(BinHeader));
SetLength(PTimeArray, BinHeader.PntCnt);
while basestream.Position<>basestream.Size do
begin
if (BinHeader.Time>0) and (BinHeader.Color=0) then
begin
BaseStream.Read(PTime, SizeOf(PTime));
PTimeArray[i]:= PTime;
Output.Append('Echo '+inttostr(BinPoints_20020715.PointEcho)+#13);
i:=i+1;
end
Вот так. Ошибок не выдает. 100% что читает правильно - проверял по отдельным частям записи. А чего там в итоге в массиве я пока не знаю... не знаю как проверить если честно.
...
Рейтинг: 0 / 0
18.04.2012, 12:39
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37758875
Фотография SergSuper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SergSuper
Участник
Freimaks,

СУБД с данными работает, а не с файлами и записями...
...
Рейтинг: 0 / 0
18.04.2012, 12:42
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37758889
Freimaks
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Freimaks
Гость
SergSuperFreimaks,

СУБД с данными работает, а не с файлами и записями...
Ну это понятно... я вроде и не говорил, что я субд хочу целый файл запихать. Я хотел туда писать данные из файла.
...
Рейтинг: 0 / 0
18.04.2012, 12:49
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37758901
Freimaks
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Freimaks
Гость
softwarerКроме того, судя по описанию, работа не разовая, а очень даже регулярная и с суммарно приличными объёмами данных.

Да, программа не для разовой работы. И объемы приличные.
Щас вот вроде разобрался с динамическим массивом, в который пишутся данные из файла.

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

Буду искать алгоритмы, ибо двойным циклом перебрать все элементы массива - это тупо (хотя в универе только это и делал).
...
Рейтинг: 0 / 0
18.04.2012, 12:54
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37758910
Фотография SergSuper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SergSuper
Участник
FreimaksSergSuperFreimaks,

СУБД с данными работает, а не с файлами и записями...
Ну это понятно... я вроде и не говорил, что я субд хочу целый файл запихать. Я хотел туда писать данные из файла.ну раз понятно - зачем Вы про всякие файлы, циклы пишите?
...
Рейтинг: 0 / 0
18.04.2012, 12:57
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37758915
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
Vladimir Baskakovя боюсь, что если не хватит объема оперативки - своп тоже что-то запишет на диск
А Вы не бойтесь :) Ещё раз: программа представляет собой трубу ввод-вывод. Она прочитала кусок входного файла, проверила на дубли, скинула в выходной - и этот кусок ей больше не нужен, она может писать в это место другие данные. Если средняя длина записи в данном случае 30 байт, а ключ дедубликации, допустим, 6 байт - значит своп в самом худшем случае наступит ку-у-уда как позже.
...
Рейтинг: 0 / 0
18.04.2012, 12:58
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37758927
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
FreimaksТеперь буду читать как хотя бы быстро проанализировать массив на одинаковые элементы и просто выдать инфу о том что они есть или их нет.
Вам не нужно этого делать. Вам нужно сделать один проход по массиву, заполняя по пути вспомогательную структуру ключами записей. Соответственно логика очень простая:

Берём очередную запись
Определяем её ключ
Если он уже есть в множестве ключей - игнорируем
Если его нет - добавляем и скидываем запись в выходной файл

Ключевой вопрос здесь - эффективно осуществлять операцию "проверили - добавили". В общем случае для этого наилучшим образом подходит структура данных hash set. Хорошие реализации хэшей для дельфи - погуглите, ибо те, что стандартно в VCL, никуда не годятся.
...
Рейтинг: 0 / 0
18.04.2012, 13:05
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37758933
Freimaks
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Freimaks
Гость
softwarerVladimir Baskakovя боюсь, что если не хватит объема оперативки - своп тоже что-то запишет на диск
А Вы не бойтесь :) Ещё раз: программа представляет собой трубу ввод-вывод. Она прочитала кусок входного файла, проверила на дубли, скинула в выходной - и этот кусок ей больше не нужен, она может писать в это место другие данные. Если средняя длина записи в данном случае 30 байт, а ключ дедубликации, допустим, 6 байт - значит своп в самом худшем случае наступит ку-у-уда как позже.
Я извиняюсь за тупой вопрос, но мне вот что не понятно - т.е. можно проводить поиск дубликатов (даже не 100%-ых, а только по нескольким полям записи) не загружая весь файл???
Можете дать ссылочку на то как это все хотя бы примерно выглядит????

P.S. Длина записи 20 байт (9 полей) + 4 байта на дополнительное поле времени+ 4 байта на поле цвета(просто время и цвет являются необязательными полями и могут как присутствовать так и нет). B 48 байт на заголовок файла. В терминологии могу путаться ибо не спец.
...
Рейтинг: 0 / 0
18.04.2012, 13:08
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37758940
Freimaks
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Freimaks
Гость
softwarerFreimaksТеперь буду читать как хотя бы быстро проанализировать массив на одинаковые элементы и просто выдать инфу о том что они есть или их нет.
Вам не нужно этого делать. Вам нужно сделать один проход по массиву, заполняя по пути вспомогательную структуру ключами записей. Соответственно логика очень простая:

Берём очередную запись
Определяем её ключ
Если он уже есть в множестве ключей - игнорируем
Если его нет - добавляем и скидываем запись в выходной файл

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

Логика работы очень понятна!! Буду искать!!! Спасибо за то, что направили на путь истинный :-)
...
Рейтинг: 0 / 0
18.04.2012, 13:10
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37758955
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
> Я извиняюсь за тупой вопрос, но мне вот что не понятно - т.е. можно проводить
> поиск дубликатов (даже не 100%-ых, а только по нескольким полям записи) не
> загружая весь файл???

Один раз надо будет файл прочитать.


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

Не подходит, поскольку совпадение хэшей не означает совпадения данных.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
18.04.2012, 13:52
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37759056
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
Dimitry SibiryakovsoftwarerВ общем случае для этого наилучшим образом подходит структура данных hash set.

Не подходит, поскольку совпадение хэшей не означает совпадения данных.

Дим, объясняю простым русским языком: тебе стоило бы слазить в гугль, прочитать о чём идёт речь и не позориться так откровенно, ориентируясь исключительно по тому, что произносимое слово звучит похоже на то, что он когда-то в другом контексте вроде как слышал. Твои выступления в этой теме звучат очень похоже на то, как если бы ты спутал hash с cash и пытался выяснить, при чём тут деньги и почему нельзя использовать бесплатный ФБ.
...
Рейтинг: 0 / 0
18.04.2012, 14:04
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37759071
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
FreimaksЯ извиняюсь за тупой вопрос, но мне вот что не понятно - т.е. можно проводить поиск дубликатов (даже не 100%-ых, а только по нескольким полям записи) не загружая весь файл???
Можно делать это, не держа весь файл единомоментно в памяти, а читая его кусками. Что даёт возможность эффективно работать с файлами, не влезающими в доступную оперативку.
...
Рейтинг: 0 / 0
18.04.2012, 14:11
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37759170
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
softwarerтебе стоило бы слазить в гугль, прочитать о чём идёт речь и не позориться так откровенно,
ориентируясь исключительно по тому, что произносимое слово звучит похоже на то, что он
когда-то в другом контексте вроде как слышал.
Ну слазил я в гугль. Ничего нового для себя не нашёл. Вопреки утверждениям о "трубе" выше,
данные всё-таки накапливаются в памяти и располагаются в массиве по порядку возрастания
хэшей. Если "упорядоченное по возрастанию расположение" нынче не считается сортировкой - я
пас, поскольку старомодно его таковой считаю.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
18.04.2012, 14:47
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37759176
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
On 04/18/2012 02:52 PM, Dimitry Sibiryakov wrote:

> Не подходит, поскольку совпадение хэшей не означает совпадения данных.

Ты прикалываешься ? Не может быть, чтобы ты был бы таким глупым и неучем.



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

Ну да, те же буквы ... A...Z, а...я ...

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

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

Короче, не лазь больше в интернет -- я тебе всё скажу:
Если B+ tree или map, или красно-чёрное дерево -- это означает, что данные
отсортированы по ключу. Если хэш-таблица -- это означает, что данные по ключу не
отсортированы.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
18.04.2012, 14:55
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37759196
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
MasterZivУпорядочение хэшей не означает упорядочение записей по ключу, даже если оно
есть. Возрастающие ключи могут давать убывающие хэши, или перемежающиеся
любым образом.
А дальше? Что же ты не продолжаешь эту мысль: "упорядочение по ключу не означает
упорядочивание данных, поскольку возрастающие данные могут давать убывающие ключи". Что же
нам теперь, case-insensitive сортировку не считать сортировкой прикажешь?..
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
18.04.2012, 15:01
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37759301
Vladimir Baskakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Vladimir Baskakov
Участник
softwarerОна прочитала кусок входного файла, проверила на дубли
а если дубль первой записи в хвосте?

допустим запись из 10 полей.
и другая запись - тоже из 10.
когда надо свистеть о совпадении - когда значение некоторого поле 1-ой записи совпало со значением 2-ой? или когда вообще все совпало?

Если совпадение - это когда комбинация первых пяти полей одного равна комбинации пяти полей другого - ага - в мясорубку их, и циферки - в кучку. Была такая циферка в кучке - надо проверять детально. Да? трубообразно. а вот если совпадение - это совпадение по 2-ум произвольным полям? все таки иметь движок, который делает груп бай - хэвинг коунт звездочка больше 1....

(может я туплю. это ничего, это бывает)
...
Рейтинг: 0 / 0
18.04.2012, 15:50
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37759338
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
MasterZivТы прикалываешься ?
Да нет. Просто изо всех сил старается сделать вид, что хоть в чём-то хоть на сколько-то прав. Некоторым людям с ранимой самооценкой и без фундамента достижений это очень важно. Не было бы этого - сказал бы, например, что последовательное чтение файла есть сортировка, поскольку читает по порядку записей в файле.

Vladimir Baskakovа если дубль первой записи в хвосте?
То нам как правило не нужна вся первая запись для того, чтобы свистнуть о совпадении.

Vladimir BaskakovБыла такая циферка в кучке - надо проверять детально.
Незачем в данном случае.

Vladimir Baskakovа вот если совпадение - это совпадение по 2-ум произвольным полям?
Не вижу смысла фантазировать. Автору всё равно лучше знать.
...
Рейтинг: 0 / 0
18.04.2012, 16:05
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37759358
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
softwarerнам как правило не нужна вся первая запись для того, чтобы свистнуть о совпадении.

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

Нет, я бы сказал, что записи в файле хранятся упорядоченными по номеру записи. А ячейки
ОЗУ - упорядочены по адресу. Есть возражения?
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
18.04.2012, 16:20
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37759437
любая операция - сортировка
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
любая операция - сортировка
Гость
Dimitry SibiryakovMasterZivУпорядочение хэшей не означает упорядочение записей по ключу, даже если оно
есть. Возрастающие ключи могут давать убывающие хэши, или перемежающиеся
любым образом.
А дальше? Что же ты не продолжаешь эту мысль: "упорядочение по ключу не означает
упорядочивание данных, поскольку возрастающие данные могут давать убывающие ключи". Что же
нам теперь, case-insensitive сортировку не считать сортировкой прикажешь?..

Ну в таком случае данные вообще везде всегда отсортированы, ведь данные располагаются в порядке адресации которая всегда идет по возрастанию, что в RAM, что в HDD :)
И любая IO-операция есть сортировка :)

Но адресацией нельзя пользоваться, т.к. совпадение адресов не означает совпадение данных.

А хэш-индексы существуют специально для того, чтобы хранить данные упорядоченными и обращаться к ним по диапазону range scan :)
...
Рейтинг: 0 / 0
18.04.2012, 16:44
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37759456
hash match group by
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hash match group by
Гость
kdvhash match group byА как это происходит и в чем преимущество данной сортировки в двух словах расскажите.
программист должен изучить все виды сортировок, и потом их применять по месту, как из "словаря". Например, я помню, что есть много разных сортировок, и чем они отличаются, но я не помню, как эти сортировки реализованы (код). Но мне это нафиг не надо - открыл любой справочник по программированию, и посмотрел.
Ну хотя бы плюсы и минусы той или иной сортировки нужно помнить, чтобы применять их к месту?
Или киньте линк на описание хэш-сортировки :)
...
Рейтинг: 0 / 0
18.04.2012, 16:48
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37759476
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
любая операция - сортировкаадресацией нельзя пользоваться, т.к. совпадение адресов не означает совпадение данных.

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

Да? А хэш-таблицы-то и не знают...

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

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

Что же
> нам теперь, case-insensitive сортировку не считать сортировкой прикажешь?..

Дальше пошла клиника -- иди, читай интернет, и попытайся вникнуть в СМЫСЛ букв.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
18.04.2012, 17:18
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37759604
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
Dimitry Sibiryakovsoftwarerнам как правило не нужна вся первая запись для того, чтобы свистнуть о совпадении.

С этого места подробнее, пожалуйста. В каких случаях для сигнализации полного
совпадения вся запись не нужна?

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

И этим ты пытаешься доказать мысль, что упорядочивание хэшей не является сортировкой?..
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
18.04.2012, 17:49
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37759878
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
любая операция - сортировка
А хэш-индексы существуют специально для того, чтобы хранить данные упорядоченными и обращаться к ним по диапазону range scan :)

С этого места будьте добры попподробнее ,
а то чуствую нужно сверить конспект и расставить заметки на полях
...
Рейтинг: 0 / 0
18.04.2012, 20:04
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37759970
любая операция - сортировка
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
любая операция - сортировка
Гость
ДохтаРлюбая операция - сортировкаА хэш-индексы существуют специально для того, чтобы хранить данные упорядоченными и обращаться к ним по диапазону range scan :)

С этого места будьте добры попподробнее ,
а то чуствую нужно сверить конспект и расставить заметки на полях
Ну вы же не будете спорить, что range scan легко провести по отсортированному массиву/таблице? (даже без индексов range-границы быстро находятся бинарным поиском)
А как нам в этой сортировке поможет "сортировка по хэшу" сейчас нам расскажет Dimitry Sibiryakov :)
Dimitry Sibiryakovhash match group byhash match group by
А сортировка по хэшу, конечно же, сортировкой не является. Ню-ню...
...
Рейтинг: 0 / 0
18.04.2012, 21:19
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37760029
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
любая операция - сортировкаА как нам в этой сортировке поможет "сортировка по хэшу" сейчас нам расскажет Dimitry
Sibiryakov :)

Легко: никак не поможет. Не делается по хэш-индексу range scan.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
18.04.2012, 21:52
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37760060
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
любая операция - сортировкаДохтаРпропущено...


С этого места будьте добры попподробнее ,
а то чуствую нужно сверить конспект и расставить заметки на полях
Ну вы же не будете спорить, что range scan легко провести по отсортированному массиву/таблице? (даже без индексов range-границы быстро находятся бинарным поиском)
А как нам в этой сортировке поможет "сортировка по хэшу" сейчас нам расскажет Dimitry Sibiryakov :)


Давайте не будем подглядывать в конспект Дмитрия.

С первой частью вопросов нет.

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

Может лекцию проспал, напомните будьте добры пруф, если вас не затруднит.

:)
...
Рейтинг: 0 / 0
18.04.2012, 22:06
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37760103
любая операция - сортировка
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
любая операция - сортировка
Гость
ДохтаРлюбая операция - сортировкапропущено...

Ну вы же не будете спорить, что range scan легко провести по отсортированному массиву/таблице? (даже без индексов range-границы быстро находятся бинарным поиском)
А как нам в этой сортировке поможет "сортировка по хэшу" сейчас нам расскажет Dimitry Sibiryakov :)


Давайте не будем подглядывать в конспект Дмитрия.

С первой частью вопросов нет.

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

Может лекцию проспал, напомните будьте добры пруф, если вас не затруднит.

:)
Сортировка по хэшу? Ну как же, вот она ссылка сортировка по хэшу
Только вот не надо, что я снова к Дмитрию подглядываю, Дмитрий не может ошибаться :)
...
Рейтинг: 0 / 0
18.04.2012, 22:33
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37760224
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
Сейчас тестеров на FVMas катастрофически не хватает. Поэтому буду предлагать именно его, продукцию новокузнецкого баянолитейного завода.
...
Рейтинг: 0 / 0
19.04.2012, 00:31
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37760229
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
Кстате в вашем случае у Юры есть интерфейс DeleteDublikaty_u. Если вы ее вызовите и она вывалится с эксепшином то дубликаты определенно есть, без вариантов.
...
Рейтинг: 0 / 0
19.04.2012, 00:39
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37760834
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
> И этим ты пытаешься доказать мысль, что упорядочивание хэшей не является
> сортировкой?..

Во-первых, хэш-коды не упорядочиваются, они просто адреса для доступа к записям.
Это грубо говоря адрес дупла, куда ты положил эту запись. Номер коробки.
во-вторых ничего доказывать и не надо -- есть факт, хэш-таблица не сортирует
записи. Если ты считаешь, что это не так -- доказывай ты, что она сортирует.
Также ещё можешь доказать, что земля плоская, солнце вращается вокруг земли,
а по небу ездит Зевс в колеснице.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
19.04.2012, 12:59
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37760955
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
MasterZivТакже ещё можешь доказать, что земля плоская,

Всем чмоки в этом чате.

Под сортировкой можно подразумевать получение из неупорядоченного (произвольного) множества упорядочного.
Делается это методом изменения физического расположения элементов в множестве или
созданием упорядоченного массива ссылок и есть суть вашей дисскуссии.

То что ключ сортировки может не очнь коррелировать с любой другой функцией от элемента множества к сути сортировки отношения не имеет.

Но это ни коем образом не имеет отношение ни к вопросу ТС, ни к вопросу Дмитрия о том, как проверить то, что множество A является подмножеством B без сортировки.
...
Рейтинг: 0 / 0
19.04.2012, 13:48
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37760974
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
ТС,
IMHO. Собственно можно взять любую, какая больше нравится (по цене, легкости администрирования, пониманию как с ней работать и т.п.).
Можно хоть embeded хоть отдельную.

Если процесс разовый (т.е. дали множество файлов и надо из них составить один без дублей), то можно посмотреть в сторону in memory database, если периодический (подкидывают новые файлы к старому множеству), то в сторону клаcсических БД.
...
Рейтинг: 0 / 0
19.04.2012, 13:58
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37760997
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
MasterZivхэш-коды не упорядочиваются, они просто адреса для доступа к записям.
Это грубо говоря адрес дупла, куда ты положил эту запись. Номер коробки.

И эти номера у вас таки не упорядоченны. Ню-ню. Покажите своё определение упорядоченности,
а то я чувствую, что оно расходится с моим...
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
19.04.2012, 14:07
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761001
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
> Всем чмоки в этом чате.
Взаимно.

>
> Под сортировкой можно подразумевать получение из неупорядоченного
> (произвольного) множества упорядочного.
> Делается это методом изменения физического расположения элементов в множестве или
> созданием упорядоченного массива ссылок и есть суть вашей дисскуссии.

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

> Но это ни коем образом не имеет отношение ни к вопросу ТС, ни к вопросу Дмитрия
> о том, как проверить то, что множество A является подмножеством B без сортировки.

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

Вообще говоря, они не обязаны быть упорядоченными.
Примером из жизни может служить адрес дома в городе.
Петровка, 38. и Божидовка 7 -- упорядочено ? Что чего меньше ?

> а то я чувствую, что оно расходится с моим...

Этот супер-мега прикол подзатянулся. Кончай придуриваться.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
19.04.2012, 14:13
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761011
Freimaks
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Freimaks
Гость
Смотрю проблема вызвала нехилый спор.
Я пока сделал не с СУБД.
Пошел по пути хранения всего в памяти.
Сделал свой класс (TBinPoints), в котором описал все возможные поля, которые могут встретится в файлах разного строения (специфика работы требует этого). Далее создал 3 конструктора, каждый соответствует одной из возможных версий файла.
Далее создал процедуру чтения с использованием TBinaryReader. Для того, чтобы это вообще работало создал три записи (packed record), которые также соответствуют версиям файлов.
В процедуре создается поток BaseStream.Read в параметрах которого вписывается нужная запись (например, BaseStream.Read(RPointsTimeColor, SizeOf(RPointsTimeColor));).
Далее в переменную (BinPoints: TBinPoints) пишется вся инфа.
Потом в действие вступает TDictionary из Generics.Collections. В ней есть специальная функция Dictionary1.AddOrSetValue (ключ, значение), которая при загрузке в нее данных уничтожает дубликаты (т.е. записи с одинаковым ключом).
В качестве ключа я попытался использовать MD5, которая считается для строки X+Y+Z+Time.
Что в итоге: все работает, но долго (даже читает медленно, по сравнению с родной программой) и занимает кучу оперативки (для файла примерно 120 Мб, заняло около 800 Мб) - все из-за MD5, но как еще считать уникальный ключ я пока не понял.
...
Рейтинг: 0 / 0
19.04.2012, 14:13
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761024
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
> В качестве ключа я попытался использовать MD5, которая считается для строки
> X+Y+Z+Time.

А на кой ? Тебе дубликаты надо удалять, или ты так, побаловаться с данными ?

> Что в итоге: все работает, но долго (даже читает медленно, по сравнению с родной
> программой) и занимает кучу оперативки (для файла примерно 120 Мб, заняло около
> 800 Мб) - все из-за MD5, но как еще считать уникальный ключ я пока не понял.

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

Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
19.04.2012, 14:17
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761038
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
MasterZivЭтот супер-мега прикол подзатянулся. Кончай придуриваться.

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

Лично я называю упорядоченным множеством такое, в котором для любого j > i выполняется
условие Xj > Xi.

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

В случае хэш-таблицы для любого j > i выполняется условие f(Xj) > f(Xi), где f - хэш
функция. Таким образом хэш-таблица удовлетворяет определению упорядоченного множества.

И процесс построения хэш-таблицы соответствует алгоритму сортировки вставками, описанной
тем же Кнутом, которого таки кое-кому полезно перечитать.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
19.04.2012, 14:22
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761041
Freimaks
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Freimaks
Гость
MasterZiv
> В качестве ключа я попытался использовать MD5, которая считается для строки
> X+Y+Z+Time.

А на кой ? Тебе дубликаты надо удалять, или ты так, побаловаться с данными ?

> Что в итоге: все работает, но долго (даже читает медленно, по сравнению с родной
> программой) и занимает кучу оперативки (для файла примерно 120 Мб, заняло около
> 800 Мб) - все из-за MD5, но как еще считать уникальный ключ я пока не понял.

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


MD5 взял просто ради проверки того, что в файле с известным мне кол-вом дубликатов этот инструмент корректно их найдет.
А щас как раз работаю над следующим шагом - созданием нормального ключа (вообще ключей, т.к. параметры разные).
...
Рейтинг: 0 / 0
19.04.2012, 14:23
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761052
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
FreimaksMD5 взял просто ради проверки того, что в файле с известным мне кол-вом дубликатов этот
инструмент корректно их найдет.

А вероятность коллизий ты учитываешь?
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
19.04.2012, 14:25
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761062
Freimaks
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Freimaks
Гость
Dimitry SibiryakovFreimaksMD5 взял просто ради проверки того, что в файле с известным мне кол-вом дубликатов этот
инструмент корректно их найдет.

А вероятность коллизий ты учитываешь?

Нет. Пока данных мало (в одном куске всего 16 точек, в другом около 500 000) я думаю коллизий не возникнет.
С MD5 покончено - тест то показал, что инструмент работает :-)
...
Рейтинг: 0 / 0
19.04.2012, 14:29
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761070
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
Dimitry SibiryakovMasterZivЭтот супер-мега прикол подзатянулся. Кончай придуриваться.

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

Лично я называю упорядоченным множеством такое, в котором для любого j > i выполняется
условие Xj > Xi.

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

В случае хэш-таблицы для любого j > i выполняется условие f(Xj) > f(Xi), где f - хэш
функция. Таким образом хэш-таблица удовлетворяет определению упорядоченного множества.

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


Сортировку тут упоминали в контексте задачи, нужно ТСу миллионы записей сортировать перед тем чтобы искать дубли или не нужно. Пришли к выводу что не нужно сортировать, хештаблица и фулскан несортированых записей.
Внутренние алгоритмы хештаблицы/мапы/сета чего угодно, как вас не касаются алгоритмы работы драйверов в Виндовс при кликаньи мышкой, ТСа не должни касаться. Сортировать ему ничего не нужно, ему нужно сканировать неупорядоченые файлы и добавлять ключи в хештаблицу. Все.
...
Рейтинг: 0 / 0
19.04.2012, 14:31
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761087
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
> В случае хэш-таблицы для любого j > i выполняется условие f(Xj) > f(Xi), где f -
> хэш
> функция.

Это неверное утверждение.

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

Мне не нужно, я своей головой думать умею.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
19.04.2012, 14:38
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761090
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
> MD5 взял просто ради проверки того, что в файле с известным мне кол-вом
> дубликатов этот инструмент корректно их найдет.
> А щас как раз работаю над следующим шагом - созданием нормального ключа (вообще
> ключей, т.к. параметры разные).

MD5 -- это хэш. Им нельзя идентифицировать запись. Поэтому оно именно НЕ НАЙДЁТ.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
19.04.2012, 14:39
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761095
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
Dimitry Sibiryakov

В случае хэш-таблицы для любого j > i выполняется условие f(Xj) > f(Xi), где f - хэш
функция. Таким образом хэш-таблица удовлетворяет определению упорядоченного множества.



Блин , это же научное открытие :)

Предлагаю срочно внести в аналы , что бы не потерялось не дай Бог.
)
...
Рейтинг: 0 / 0
19.04.2012, 14:41
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761097
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
MasterZivЭто неверное утверждение.

Да неужели?.. И в чём же ты видишь его неверность?
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
19.04.2012, 14:41
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761102
Freimaks
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Freimaks
Гость
MasterZivТ.е. ключём должен быть массив пар "название поля"-"значение поля".

А не подскажите как этот массив сформировать? Учитывая, что совпадающими могут быть 4 поля?
...
Рейтинг: 0 / 0
19.04.2012, 14:43
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761127
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
Дмитрий , поздравляю вы на границе открытия , над которым ученные мужи ломают мозги уже десятки лет.


Dimitry Sibiryakov
В случае хэш-таблицы для любого j > i выполняется условие f(Xj) > f(Xi), где f - хэш
функция. Таким образом хэш-таблица удовлетворяет определению упорядоченного множества.



Dimitry SibiryakovА вероятность коллизий ты учитываешь?


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


Единственное осталось , избавить вашу теорию от взаимоисключающих параграфов.
...
Рейтинг: 0 / 0
19.04.2012, 14:49
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761133
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
ДохтаРЕдинственное осталось , избавить вашу теорию от взаимоисключающих параграфов.

Это легко: достаточно заменить "f(Xj) > f(Xi)" на "f(Xj) >= f(Xi)".
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
19.04.2012, 14:51
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761165
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
Dimitry SibiryakovДохтаРЕдинственное осталось , избавить вашу теорию от взаимоисключающих параграфов.

Это легко: достаточно заменить "f(Xj) > f(Xi)" на "f(Xj) >= f(Xi)".


Еще раз :

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


Корреляцию пападения в взаимоисключающие параграфы видите ?

Ваши функции туда попадают чуть более более чем со 100% вероятностью )
...
Рейтинг: 0 / 0
19.04.2012, 15:03
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761184
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
On 04/19/2012 03:41 PM, ДохтаР wrote:

> Блин , это же научное открытие :)
>
> Предлагаю срочно внести в аналы
> < http://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5>
> , что бы не потерялось не дай Бог.
> )

Внесите!
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
19.04.2012, 15:09
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761188
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
On 04/19/2012 03:41 PM, Dimitry Sibiryakov wrote:

> MasterZiv
> Это неверное утверждение.
>
>
> Да неужели?.. И в чём же ты видишь его неверность?

В его содержании, естественно :-)
Это утверждение ложно.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
19.04.2012, 15:10
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761190
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
Сергей АрсеньевПод сортировкой можно подразумевать получение из неупорядоченного (произвольного) множества упорядочного.
Не просто "упорядоченного", а "упорядоченного по некоему заранее заданному критерию". При этом на практике применимость того или иного алгоритма сортировки определяется в том числе спектром критериев, которые он в состоянии обслужить.

Дмитрий же делает вид, что сортировкой является упорядочивание по некоему случайному критерию, определяемому в процессе собственно упорядочивания. Как это... "Сортирую слепым методом, 14 миллиардов элементов в секунду. Только такая фигня получается" (ц)
...
Рейтинг: 0 / 0
19.04.2012, 15:11
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761193
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
FreimaksВ качестве ключа я попытался использовать MD5, которая считается для строки X+Y+Z+Time.
Тыб еще SHA1024 взял. Тебе не надо обратной невосстановимости, тебе скорость нужна. Возми чего попроще (хоть CRC или последовательный XOR байтов).
Ну и по хешу надо запоминать список вариантов значений полей ему уодвлетворяющий.

Хотя в твоем случае если значений полей встречаются более-менее равномерно, то хеш тут совсем не нужен. Просто запоминаешь в ассоциативном массиве [Поле1][Поле2]...
...
Рейтинг: 0 / 0
19.04.2012, 15:11
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761203
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
On 04/19/2012 03:43 PM, Freimaks wrote:

> А не подскажите как этот массив сформировать? Учитывая, что совпадающими могут
> быть 4 поля?

НУ...
я дельфы не знаю, берёшь какой-то список или динамический массив,
берёшь делаешь структуру из пар (имя - значение)
и запихиваешь в этот массив или список пары (имя - значение).

Можно имя поля не использовать, а использовать соглашение,
что например это будет массив 4 значений,
1-ое значение -- поле 1
2-ое значение -- поле 2
и так далее.

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

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

Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
19.04.2012, 15:14
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761208
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
On 04/19/2012 03:51 PM, Dimitry Sibiryakov wrote:

> Единственное осталось , избавить вашу теорию от взаимоисключающих параграфов.
>
>
> Это легко: достаточно заменить "f(Xj) > f(Xi)" на "f(Xj) >= f(Xi)".

Давай остановимся всё же на

f(Xj) <=> f(Xi)

(где <=> -- означает естественно "меньше, равно или больше"

Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
19.04.2012, 15:16
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761213
Freimaks
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Freimaks
Гость
Щас переделал так:
В Type прописал новый объект TPair, состоящий из 4 полей (X,Y,Z,Time). Завел переменную Pair:TPair;
Далее при чтении файла заполняются эти 4 поля и в TDictionary используются как ключ в виде переменной Pair. Но памяти жрет опять же немерено - на файл в 126 Мб, отъедается около 400 Мб.
...
Рейтинг: 0 / 0
19.04.2012, 15:18
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761217
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
> Тыб еще SHA1024 взял. Тебе не надо обратной невосстановимости, тебе скорость
> нужна. Возми чего попроще (хоть CRC или последовательный XOR байтов).
> Ну и по хешу надо запоминать список вариантов значений полей ему уодвлетворяющий.

Блин, ещё один. Ему надо дубликаты искать, ему нельзя никакие свёртки
использовать. Надо сами значения уникальных полей.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
19.04.2012, 15:19
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761225
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
> В Type прописал новый объект TPair, состоящий из 4 полей (X,Y,Z,Time).

Да, похоже маразм -- это заразное... (чур меня, чур).

> Далее при чтении файла заполняются эти 4 поля и в TDictionary используются как
> ключ в виде переменной Pair. Но памяти жрет опять же немерено - на файл в 126
> Мб, отъедается около 400 Мб.

Ну а куда деваться -то ?
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
19.04.2012, 15:21
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761234
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
softwarerНе просто "упорядоченного", а "упорядоченного по некоему заранее заданному критерию".
Хотелось бы пояснить, чем просто "упорядоченного" отличается от "упорядоченного по некоему заранее заданному критерию" и возможно ли первое без второго?

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

Дискутировать на эту тему можно долго. И безпонтово. Как и о том, что эффективнее дерево или hash таблица. Первое сложно строить - второе может быть неэффективно на конкретных данных.
...
Рейтинг: 0 / 0
19.04.2012, 15:23
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761241
Freimaks
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Freimaks
Гость
MasterZiv> В Type прописал новый объект TPair, состоящий из 4 полей (X,Y,Z,Time).
Да, похоже маразм -- это заразное... (чур меня, чур).
> Далее при чтении файла заполняются эти 4 поля и в TDictionary используются как
> ключ в виде переменной Pair. Но памяти жрет опять же немерено - на файл в 126
> Мб, отъедается около 400 Мб.

Ну а куда деваться -то ?

Сори, если что-то пропустил - уже столько всего тут написали. А как еще действовать если не так???
Т.е. грубо говоря - этот инструмент сам удаляет дубликаты, наличие дубликатов определяется по одинаковому ключу, соответственно этот ключ надо как-то сформировать. Единственное что мне пришло в голову - считать сумму, но подсказали по поводу пар - я переделал на пары... работает пошустрее конечно, но не идеально, кто же спорит.
...
Рейтинг: 0 / 0
19.04.2012, 15:25
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761324
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
MasterZivЭто утверждение ложно.
Но привести доказательство его ложности Вы, конечно же, откажетесь...

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

Дмитрий же делает вид, что сортировкой является упорядочивание по некоему случайному
критерию, определяемому в процессе собственно упорядочивания.
Э-э-э... Александр, Вы хэш-функцию считаете "случайным критерием"? Утверждаете её
недетерминированность? Или на каком ещё основании Вы утверждаете, что в процессе
построения хэш-таблицы не происходит упорядочение множества по возрастанию значения хэшей
его элементов?
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
19.04.2012, 15:48
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761362
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
FreimaksА как еще действовать если не так???
Вы пробовали построить массив массивов или нет?
...
Рейтинг: 0 / 0
19.04.2012, 16:04
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761379
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
Dimitry SibiryakovMasterZivЭто утверждение ложно.
Но привести доказательство его ложности Вы, конечно же, откажетесь...

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

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


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

Поэтому хеш от 1 может быть 45456456, а от 1000000000 может быть 54,
никаких требований "для сортировки" у хешфункции нет и быть не может.
...
Рейтинг: 0 / 0
19.04.2012, 16:11
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761385
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
Сергей АрсеньевХотелось бы пояснить, чем просто "упорядоченного" отличается от "упорядоченного по некоему заранее заданному критерию" и возможно ли первое без второго?
Конечно, возможно. Представьте себе, например, что мы вставили в некую таблицу 100 записей и затем выбираем их select-ом. Мы увидим их в каком-то порядке, но отсортирована ли выборка?

Сергей Арсеньев Дмитрий же хотел сказать, что построение hash таблицы есть частный случай неоднозначного упорядочивания
Дмитрий хотел сказать, что автомобиль содержит лошадиные силы и поэтому его утверждение, что мы постоянно ездим на лошадях, вполне истинно.
...
Рейтинг: 0 / 0
19.04.2012, 16:14
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761397
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
BazistВ данном случае, единственное требование к хешфункции это более-менее равномерное распределение значений по диапазону,
что исключит частые коллизии.
Если быть точным, то лучше сформировать другое требование: время вычисления хеш функции и поиска записи ей соответствующей должно чаще всего быть меньше времени перебора коллизий.
...
Рейтинг: 0 / 0
19.04.2012, 16:17
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761401
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
softwarerПредставьте себе, например, что мы вставили в некую таблицу 100 записей и затем выбираем
их select-ом. Мы увидим их в каком-то порядке, но отсортирована ли выборка?

rownum в ней монотонно возрастает, нет?..
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
19.04.2012, 16:18
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761405
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
softwarerМы увидим их в каком-то порядке, но отсортирована ли выборка?
Вопрос не менее мощный чем основной вопрос философии (ну тот, про курицу и яйцо).
...
Рейтинг: 0 / 0
19.04.2012, 16:19
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761408
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
Dimitry Sibiryakovrownum в ней монотонно возрастает, нет?..
Дмитрий, тут Вы перегинаете палку - отсортированный, это не тот который в определенном порядке, это тот, который отсортировали.
...
Рейтинг: 0 / 0
19.04.2012, 16:21
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761422
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Сергей Арсеньевотсортированный, это не тот который в определенном порядке, это тот, который отсортировали.

<sarkazm on>Вы ещё добавьте "методом пузырька"...<sarkazm off>
Зачем такие ограничения на процесс? Главное - результат.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
19.04.2012, 16:26
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761440
Freimaks
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Freimaks
Гость
Сергей АрсеньевFreimaksА как еще действовать если не так???
Вы пробовали построить массив массивов или нет?
Чтобы не вводить в заблуждение, признаюсь - я даже не знаю что это такое.
...
Рейтинг: 0 / 0
19.04.2012, 16:31
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761448
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
Dimitry SibiryakovЭ-э-э... Александр, Вы хэш-функцию считаете "случайным критерием"?
Да, безусловно.

Dimitry SibiryakovУтверждаете её недетерминированность?
Её (не)детерминированность не имеет отношения к моему утверждению. Не надо демагогически подменять тему, ни здесь, ни в следующем предложении.

Dimitry SibiryakovИли на каком ещё основании Вы утверждаете,
На том основании, что когда я смотрю на данные, например

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
SQL> select object_id, object_name, object_type, last_ddl_time
  2  from dba_objects
  3  where last_ddl_time > date '2010-04-03' and rownum <= 10;
 
 OBJECT_ID OBJECT_NAME          OBJECT_TYP LAST_DDL_TIME
---------- -------------------- ---------- --------------------
       723 STREAMS$_DEF_PROC    TABLE      08.04.2011 12:35:53
       910 OLAP_DESCRIPTIONS$   TABLE      08.04.2011 12:35:53
      1138 IDGEN1$              SEQUENCE   08.04.2011 12:32:49
      4891 DBMS_LOCK            PACKAGE    14.03.2012 11:15:53
      5048 UTL_RECOMP_SORTED    TABLE      08.04.2011 12:36:22
      5049 UTL_RECOMP_COMPILED  TABLE      08.04.2011 12:36:22
      6174 WRH$_FILESTATXS      TABLE      18.04.2012 23:34:22
      6198 WRH$_SQLSTAT         TABLE      18.04.2012 23:34:23
      6221 WRH$_SYSTEM_EVENT    TABLE      18.04.2012 23:34:24
      6233 WRH$_WAITSTAT        TABLE      18.04.2012 23:34:24

я могу сказать, к какому результату приведёт сортировка по тому или иному (простому) критерию. Например, я знаю, какой результат даст сортировка по полю OBJECT_NAME, не зная при этом деталей реализации алгоритма сортировки и допуская замену его на какой-либо другой.

Когда я дам Вам интерфейс к некоей реализации хэш-таблицы, и

Вы сможете предсказать, как она упорядочит данные

Вы сможете, опираясь на неё и без использования других средств сортировки отсортировать данные, например, по полю OBJECT_NAME

Ваша реализация выдержит замену хэш-таблицы на другую с тем же интерфейсом и другой реализацией

Вы убедительно докажете, что хэширование является сортировкой. Поскольку это Вам не под силу - я имею полное основание утверждать, что Вы в очередной раз занимаетесь безответственным словоплётством.
...
Рейтинг: 0 / 0
19.04.2012, 16:34
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761458
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
FreimaksЧтобы не вводить в заблуждение, признаюсь - я даже не знаю что это такое.
Массив в элементак хоторого хранится другой массив. :)

В Вашей версии Delphi Есть TBucketList? Если да то строите
[X][Y][Z][Time]

И если такой элемент уже есть, то вуаля -дубль.
...
Рейтинг: 0 / 0
19.04.2012, 16:38
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761462
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
softwarerВы убедительно докажете, что хэширование является сортировкой.

Оно мне надо? Я нигде не утверждал, что хэширование является сортировкой. Я утверждал, что
хэш-таблица унутре держит данные отсортированными, и не более того.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
19.04.2012, 16:39
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761463
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
Dimitry Sibiryakov<sarkazm on>Вы ещё добавьте "методом пузырька"...<sarkazm off>
Зачем такие ограничения на процесс? Главное - результат.
Вопрос терминологии, собственно наличием процесса "упорядоченное множество" и отличается от "отсортированного".
...
Рейтинг: 0 / 0
19.04.2012, 16:40
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761466
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
> Сори, если что-то пропустил - уже столько всего тут написали. А как еще
> действовать если не так???

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

С нетерпением жду Вашей реплики о том, что выбранная Вами саркастическая форма подчёркивает Ваше безоговорочное согласие с оппонентом.
...
Рейтинг: 0 / 0
19.04.2012, 16:55
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761489
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
softwarerГлупая ложь.
Где в выражении "сортировка по хэшу" Вы смогли прочитать "хеширование это сортировка"?
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
19.04.2012, 16:59
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761508
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
> Но привести доказательство его ложности Вы, конечно же, откажетесь...
>

Я тебе уже говорил -- хочешь доказать, что это истино -- доказывай.

Ну, если хочешь, изволь.

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

M >> m.

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

-- h1 != h2
---- h1 < h2
---- h1 > h2
-- h1 == h2
((1))

Предположим, что R1 < R2 в смысле порядка следования ключа.

но по ((1)) мы можем попасть на случай, когда

h1 == h2 и тогда при R1 < R2 мы получим, что Fh(R1) == Fh(R2), т.е.
в то время, как записи по порядку ключа следуют в R1,R2 , хэш-функции
от этих записей по порядку равновелики.

Рассмотрим другой случай, когда

h1 != h2 и h1 > h2

тогда при R1 < R2 мы получим, что Fh(R1) > Fh(R2), т.е.
в то время, как записи по порядку ключа следуют в R1,R2 , хэш-функции
от этих записей по порядку следуют Fh(R2), Fh(R1).

Третий случай даст сохранение порядка. R1,R2 => Fh(R1), Fh(R2)

Как выбираются один из трёх вариантов ((1)) ? Это зависит от хэш-функции.
Путём выбора функции мы можем исключать какие-то случаи из трёх.
Но очевидно, что случай h1 == h2 исключён быть не может, поскольку исходя из
определения хэш-функции M >> m. Следовательно, частичный порядок
исходных записей не может быть сохранён в виде порядка их хэш-функций --
часть записей, которые были не равны друг другу в порядке, могут стать
равными друг другу в порядке следования их хэш-функций.












Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
19.04.2012, 17:05
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761521
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
> Представьте себе, например, что мы вставили в некую таблицу 100 записей и затем
> выбираем
> их select-ом. Мы увидим их в каком-то порядке, но отсортирована ли выборка?

> rownum в ней монотонно возрастает, нет?..

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

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

(под множеством понимается множество элементов данной последовательности,
конечное, а не множество всех возможных элементов, существующих в природе).

Блин, жалко, что эти зануды-математики уже давно придумали этот закон...
Эту теорему, что любое конечное множество является счётным.


Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
19.04.2012, 17:14
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761522
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
> rownum в ней монотонно возрастает, нет?..
>
>
> Дмитрий, тут Вы перегинаете палку - отсортированный, это не тот который в
> определенном порядке, это тот, который отсортировали.

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

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

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


А это как понимать ?

Dimitry SibiryakovВ случае хэш-таблицы для любого j > i выполняется условие f(Xj) > f(Xi), где f - хэш
функция. Таким образом хэш-таблица удовлетворяет определению упорядоченного множества.


Расшифруйте , будьте так добры.
...
Рейтинг: 0 / 0
19.04.2012, 18:05
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761706
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
ДохтаРА это как понимать ?
Дословно:
1) Данные помещаются в хэш-таблицу.
2) Значение хэша служит индексом в этой таблице.
3) Таблицы упорядочена по возрастанию индекса.

i и j в данном случае - индексы элементов хэш-таблицы. То есть сами значения хэшей.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
19.04.2012, 18:36
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761715
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
Dimitry Sibiryakovi и j в данном случае - индексы элементов хэш-таблицы. То есть сами значения хэшей.
Расскажите тогда уж, что такое Xi, Xj, F(Xi) и F(Xj) соответственно
...
Рейтинг: 0 / 0
19.04.2012, 18:38
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761727
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
softwarerРасскажите тогда уж, что такое Xi, Xj, F(Xi) и F(Xj) соответственно

Xj, Xj - элементы хэш-таблицы. F(Xi), F(Xj) - значения хэшей этих элементов.

Будете возражать, что в хэш-таблице элемент с большим хэшем имеет больший индекс?..
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
19.04.2012, 18:42
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761729
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Dimitry SibiryakovБудете возражать
* То бишь "пытаться опровергнуть".
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
19.04.2012, 18:44
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761745
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
Dimitry Sibiryakovi и j в данном случае - индексы элементов хэш-таблицы. То есть сами значения хэшей.
Dimitry SibiryakovXj, Xj - элементы хэш-таблицы. F(Xi), F(Xj) - значения хэшей этих элементов.
То есть i = F(Xi) и j = F(Xj), я всё правильно понял?
...
Рейтинг: 0 / 0
19.04.2012, 18:46
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761777
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
Dimitry SibiryakovsoftwarerРасскажите тогда уж, что такое Xi, Xj, F(Xi) и F(Xj) соответственно

Xj, Xj - элементы хэш-таблицы. F(Xi), F(Xj) - значения хэшей этих элементов.

Будете возражать, что в хэш-таблице элемент с большим хэшем имеет больший индекс?..



Давайте вспомним с чего все началось

12430306

Dimitry Sibiryakov....ему для сортировки и поиска дубликатов позарез....


Данные вроде как упорядочить нужно, а не ......

Какое отношение все что вы тут пишете имеет к упорядочиванию реальных данных ?
...
Рейтинг: 0 / 0
19.04.2012, 18:59
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761786
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
ДохтаРДавайте вспомним с чего все началось
Cтойте, Дохтар! Не мешайте пациенту доказывать великую теорему "если i > j, то i > j"
...
Рейтинг: 0 / 0
19.04.2012, 19:02
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761797
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
softwarerТо есть i = F(Xi) и j = F(Xj), я всё правильно понял?

Правильно.

ДохтаРКакое отношение все что вы тут пишете имеет к упорядочиванию реальных данных ?

Прямое. Они при помещении в хэш-таблицу упорядочиваются, нет?..
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
19.04.2012, 19:13
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761811
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
Dimitry SibiryakovsoftwarerТо есть i = F(Xi) и j = F(Xj), я всё правильно понял?

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

Вопрос, конечно, на усмотрение модератора, но лично я предлагаю забанить за троллинг. Например, на недельку.
...
Рейтинг: 0 / 0
19.04.2012, 19:22
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761816
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
прошу прощения , что путаю хронологический порядок(сортировку) постов при цитировании .

Dimitry SibiryakovsoftwarerТо есть i = F(Xi) и j = F(Xj), я всё правильно понял?

Правильно.

ДохтаРКакое отношение все что вы тут пишете имеет к упорядочиванию реальных данных ?

Прямое. Они при помещении в хэш-таблицу упорядочиваются , нет?..


Это утверждение ?


Dimitry SibiryakovОно мне надо? Я нигде не утверждал , что хэширование является сортировкой. Я утверждал, что
хэш-таблица унутре держит данные отсортированными, и не более того.


Уже можно считать , что утверждали , или еще нет ?
...
Рейтинг: 0 / 0
19.04.2012, 19:25
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761822
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
softwarerDimitry Sibiryakovпропущено...

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

Вопрос, конечно, на усмотрение модератора, но лично я предлагаю забанить за троллинг. Например, на недельку.

Я прошу прощения, я против бана.
Любому человеку свойственно заблуждаться и не запрещено аргументированно доказывать свои заблуждения.
Ресурс скатывается в унылое Г , согласитесь интересных технических тем все меньше и меньше.
...
Рейтинг: 0 / 0
19.04.2012, 19:29
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761834
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
ДохтаРЯ прошу прощения, я против бана.
Любому человеку свойственно заблуждаться и не запрещено аргументированно доказывать свои заблуждения.
Разве ж кто-то выступает против заблуждений? Они закончились ещё на первой странице, отправкой неграмотных в гугль. Потом это перешло в известные большинству по песочнице психологические игры. А вот когда дошло до математически доказанного троллинга - уже вполне пора в бан, имхо.
...
Рейтинг: 0 / 0
19.04.2012, 19:40
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761866
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
Любая аргументация по сути есть психологические игры.
Любые психологические игры ( наталкивание оппонента на мысль) через сарказм,
или даже просто доп информация для размышлений - вброс.

Любая дисскуссия при желании математически сокращается до формулы троллинга.

НО фильтровать то нужно по однозначным критериям троллинга, переход на личности, оскарбления и т д
Их небыло( я не увидел) , по этому повода кого либо банить я не вижу.
...
Рейтинг: 0 / 0
19.04.2012, 20:05
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761870
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
softwarerТаким образом, больной признался, что использовал принципиально разные
обозначения для одних и тех же понятий для превращения банальной тавтологии в нечто вроде
как солидно выглядящее (для первоклассника).
Вообще-то я просто рассказал как работают хэш-таблицы. У них действительно i=F(Xi). Если
для тебя это новость - сочувствую, но помочь ничем не могу.

А если для тебя также новость, что при сортировке у элементов множества меняются индексы -
это вообще клиника.

ДохтаРУже можно считать , что утверждали , или еще нет ?

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

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


Ок, продолжаем разговор

Вброс ОН
Дмитрий , у меня ту еще в конспекте непонятки , еще в пару заметки на полях поставить нужно.

Собственно вопрос , построение хеш таблицы для последующего быстрого поиска ( реальных данных) как происходит ?
Вы хотите сказать, что результаты хеш функций хранящиеся в таблице поддерживают одновременно 2 порядка.
Один для быстрого поиска ключей , другой для сортировки реальных данных ?

Как идиоту разжуйте , что бы понятно было , будьте так добры

Вброс ОФФ
...
Рейтинг: 0 / 0
19.04.2012, 20:24
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761888
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
Люди читать этот флейм, как бальзам на душу.

Предлагаю маленькую задачку. Кто решит - может считать себя гуру данного флейма.

Дано. Метрика сортировки не изменяется. После сортировки множество не меняется.
привести пример отсортированного и неупорядоченного множества.

 
Hint: подобное не предлагать
Код: sql
1.
select * from dual group by dbms_random.value

...
Рейтинг: 0 / 0
19.04.2012, 20:27
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761897
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
Сергей АрсеньевЛюди читать этот флейм, как бальзам на душу.

Предлагаю маленькую задачку. Кто решит - может считать себя гуру данного флейма.

Дано. Метрика сортировки не изменяется. После сортировки множество не меняется.
привести пример отсортированного и неупорядоченного множества.

+
 
Hint: подобное не предлагать
Код: sql
1.
select * from dual group by dbms_random.value



Код: plsql
1.
2.
select a, b  from table
order by a asc , b desc



По а отсортировано правильно , по в упорядочено не правильно( не упорядочено )

Приблизительно так
.
...
Рейтинг: 0 / 0
19.04.2012, 20:32
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761916
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
ДохтаР,

Множество у тебя одно из пар элементов. Не зачет.

P.S. Кстати у меня там ошибка в стиле данного топика. Вместо group by следует читать order by.
...
Рейтинг: 0 / 0
19.04.2012, 20:56
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761918
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
ДохтаРВы хотите сказать, что результаты хеш функций хранящиеся в таблице поддерживают
одновременно 2 порядка.
Один для быстрого поиска ключей , другой для сортировки реальных данных ?

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

Нет. Из какого пальца Вы высосали такую странную идею?


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

Вопрос очень пересекается с вопросом Сергея.
Ответите , будет признаны гуру топика.
...
Рейтинг: 0 / 0
19.04.2012, 21:40
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761972
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
Сергей Арсеньев P.S. Кстати у меня там ошибка в стиле данного топика. Вместо group by следует читать order by.
У Вас там нет ошибки, group by и order by в этом случае дадут одинаковый результат
...
Рейтинг: 0 / 0
19.04.2012, 21:42
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37761978
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
Сергей АрсеньевДохтаР,

Множество у тебя одно из пар элементов. Не зачет.

P.S. Кстати у меня там ошибка в стиле данного топика. Вместо group by следует читать order by.

А где в постановке сказано, что каждый элемент множдества имеет единственный атрибут ?
Формально я условия задачи выполнил )

В сабжевой задаче ничего про хеш ключи не сказано, но это не помешало нам
уделить их сортировке больше внимания , чем сортировке реальных данных.
...
Рейтинг: 0 / 0
19.04.2012, 21:45
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37762018
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
ДохтаРЯ ничего не высасывал , я вашу логику пытаюсь понять,
Как хеш таблица одновременно организует быстрый поиск и порядок следования оригинальных
данных.

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

А я понять не могу откуда Вы взяли странную идею, что она сохраняет порядок следования данных.


А почему идею, Вы предыдущей странице это констатировали ,

Dimitry SibiryakovДохтаРКакое отношение все что вы тут пишете имеет к упорядочиванию реальных данных ?

Прямое. Они при помещении в хэш-таблицу упорядочиваются......


я законспектировал и задаю вопросы потому , что мне еще не все понятно :
...
Рейтинг: 0 / 0
19.04.2012, 22:33
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37762052
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
ДохтаРА почему идею, Вы предыдущей странице это констатировали

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

Я кажется начинаю понимать , теперь для полного прояснения ситуации и растановки точек на Ё
приведите пожалуйста какой нибудь другой пример из реальной жизни
отвечающий условиям задачи
12442105
...
Рейтинг: 0 / 0
19.04.2012, 22:57
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37762078
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Точки над Ё пусть Ё и расставляет. Я из этого "условия задачи" ни слова не понял.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
19.04.2012, 23:08
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37762098
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
Dimitry SibiryakovДохтаРА почему идею, Вы предыдущей странице это констатировали

Эта... "упорядочиваться" означает "изменять порядок" вообще-то. С "сохранением порядка"
оно как бэ полные противоположности...


А кто говорит про сохранение ?

Мы про изменение (сортировку ) говорим.

Так как упорядочатся реальные данный в хеш-таблице ?

По по какому закону или критерию ?
...
Рейтинг: 0 / 0
19.04.2012, 23:18
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37762110
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
ДохтаРА где в постановке сказано, что каждый элемент множдества имеет единственный атрибут ?
Формально я условия задачи выполнил )
Ни разу. У Вас множество упорядоченное по a? Упорядоченное. А требуется неупорядоченное.
Причем сразу поясняю по той метрике, по которой сортировали.
...
Рейтинг: 0 / 0
19.04.2012, 23:30
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37762118
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
ДохтаРТак как упорядочатся реальные данный в хеш-таблице ?

По по какому закону или критерию ?
По возрастанию значения хэша, натурально.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
19.04.2012, 23:33
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37762124
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
еееееее
хештаблы опять в зените 10748507
...
Рейтинг: 0 / 0
19.04.2012, 23:37
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37762145
идеально бы вписался
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
идеально бы вписался
Гость
Эх не хватает Bazist'a с его рассуждениями, идеально бы вписался.
...
Рейтинг: 0 / 0
20.04.2012, 00:04
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37762150
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
Dimitry SibiryakovsoftwarerРасскажите тогда уж, что такое Xi, Xj, F(Xi) и F(Xj) соответственно

Xj, Xj - элементы хэш-таблицы. F(Xi), F(Xj) - значения хэшей этих элементов.
гл
Будете возражать, что в хэш-таблице элемент с большим хэшем имеет больший индекс?..



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

Так , тоже самое множество неупорядочено по в, разве упорядочено ?

Метрика как бы тоже одна order by a asc, b desc и не меняется.

Вам нужно упорядоченное смотрите в а
нужно не упорядоченное смотрите в .

зы Постановка мне напоминает задачу ( административную) , в которое не зависимо от предоставленного результата следут заявление , вы все неправильно поняли , переделывайте , и так по кругу.
Вы шо думаете я ее буду переделывать , не )) , решение формально удовлетворяет любую хотелку заказчика.
...
Рейтинг: 0 / 0
20.04.2012, 00:14
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37762162
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
> Дословно:
> 1) Данные помещаются в хэш-таблицу.
> 2) Значение хэша служит индексом в этой таблице.
> 3) Таблицы упорядочена по возрастанию индекса.
>
> i и j в данном случае - индексы элементов хэш-таблицы. То есть сами значения хэшей.

Короче, сразу видно, что ты даже ни разу не пользовался хэш-таблицей никогда.
Индексом в хэш-таблице служит ключ данных, а хэш-функцию и её результат ты
никогда и не видишь. Кроме того, в современных хэш-таблицах функция эта ещё
и переменная, она меняется со временем.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
20.04.2012, 00:29
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37762167
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
Пока больному легче, доктор может и поспать...
...
Рейтинг: 0 / 0
20.04.2012, 00:39
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37762168
ДохтаР
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ДохтаР
Участник
Сергей АрсеньевДохтаРА где в постановке сказано, что каждый элемент множдества имеет единственный атрибут ?
Формально я условия задачи выполнил )
Ни разу. У Вас множество упорядоченное по a? Упорядоченное. А требуется неупорядоченное.
Причем сразу поясняю по той метрике, по которой сортировали.

Кстате ,

Код: plsql
1.
2.
select a  from table
order by b



Так устроит ?
...
Рейтинг: 0 / 0
20.04.2012, 00:39
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37762358
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
ДохтаРТак , тоже самое множество неупорядочено по в, разве упорядочено ?

Вы не поверите, оно еще не упорядочено и по c и по random и по много чему еще.
Хорошо в первоначальной постановки задачи отсутствовало пояснение, что подразумевается один и тот же порядок как в сортировке, так и в проверке на упорядоченность.
...
Рейтинг: 0 / 0
20.04.2012, 09:45
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37762578
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
MasterZivИндексом в хэш-таблице служит ключ данных
А адресного пространства хватит на данные с ключом размером в пару килобайт?..
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
20.04.2012, 11:31
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37762581
sphinx_mv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
sphinx_mv
Участник
MasterZiv
> Дословно:
> 1) Данные помещаются в хэш-таблицу.
> 2) Значение хэша служит индексом в этой таблице.
> 3) Таблицы упорядочена по возрастанию индекса.
>
> i и j в данном случае - индексы элементов хэш-таблицы. То есть сами значения хэшей.

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

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

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

При необходимости часто делать выборки из больших таблиц по точному совпадению в полях больших размеров (например, текстовых идентификаторов), для ускорения поиска и уменьшения места, занимаемого индексами физической таблицы, можно использовать индекс по значению хэш-функции для этого конкретного поля. Соотвественно, в условии выборки используется уже не значение поля, а значение хэш-функции от кроиерия выборки по этому полю. Естественно, что не следует забывать про возможные коллизии при этом.
...
Рейтинг: 0 / 0
20.04.2012, 11:32
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37762699
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
On 04/20/2012 12:31 PM, Dimitry Sibiryakov wrote:

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

Браво, Дмитрий, пиши ещё!
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
20.04.2012, 12:21
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37762717
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
> У меня сложилось подозрение, что Вы сильно зауживаете понятие и использование
> хэш-функций и хэш-таблиц.
> По сути UPPER, LOWER, не говоря уже о SOUNDEX, тоже могут считаться
> хэш-функциями, а индексы в БД - хэш-таблицами.

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


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

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

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

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

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

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

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


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

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

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

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

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


Да, именно так и есть. Поскольку хорошую равномерную хешфункцию можно выбрать только зная все элементы массива.
При большом количестве элементов растет количество коллизий и хештаблица выраждается в унылый тормоз если хешфункция подобрана неудачно для этого ряда.
...
Рейтинг: 0 / 0
20.04.2012, 12:59
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37762862
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
О сколько Диме открытий чудных,
готовит просвещенья век (с)
...
Рейтинг: 0 / 0
20.04.2012, 13:10
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37762875
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
BazistПри большом количестве элементов растет количество коллизий и хештаблица выраждается в унылый тормоз если хешфункция подобрана неудачно для этого ряда.
Поэтому в индексах чаще и используют деревья, сруктура которых по сути и является динамической hash функцией. Но естественно требует дополнительных затрат на постоянное обновление.

P.S. Я понимаю, что за обсуждение действий модераторов тут банят, чуть ли не пожизненно, но Дмитрий всего лишь процитировал то, что ему написали несколькими страницами ранее.
...
Рейтинг: 0 / 0
20.04.2012, 13:14
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37762882
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
Bazist О сколько Диме открытий чудных,
готовит просвещенья век (с)
А теперь в кратце, Вы тоже считаете, что хеш таблица не упорядоченна, потому что ее порядок не соответствует некому мифическому ключу?
...
Рейтинг: 0 / 0
20.04.2012, 13:16
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37762895
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
MasterZivПерехэширование.

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

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

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

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



Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
20.04.2012, 13:22
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37762903
sphinx_mv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
sphinx_mv
Участник
MasterZiv
> У меня сложилось подозрение, что Вы сильно зауживаете понятие и использование
> хэш-функций и хэш-таблиц.
> По сути UPPER, LOWER, не говоря уже о SOUNDEX, тоже могут считаться
> хэш-функциями, а индексы в БД - хэш-таблицами.

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

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

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

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

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

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

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

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

Давай тыкнем пальцем на хаос и скажем что он особым образом упорядочен.
Что мне с "упорядочиваний" хештаблицы если я не могу вытянуть элементы в сортированом порядке по ключу, не могу вытягивать элементы по диапазону ключей и так далее ? Что собсно могу сделать например в тех же структурах аля дерево, где элементы действительно упорядочены в алфавитном порядке. Как хештаблице удобней, так она их и "упорядочивает" тоесть это ее внутренние потребности как и в каком порядке будет разлаживать элементы. Для клиента этот черный ящик с недетрменированым порядком.
...
Рейтинг: 0 / 0
20.04.2012, 13:24
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37762907
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
sphinx_mvПо сути UPPER, LOWER, не говоря уже о SOUNDEX, тоже могут считаться хэш-функциями,
Только очень теоретически. Они практически неприменимы в тех ситуациях, в которых мы хотим применять хэш-функции.

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

sphinx_mvСоответствеенно, и сама хэш-функция известна, и доступ к ее результату тоже имеется.
Пусть имеется. Я не зря писал в своих требованиях про возможность замены хэш-функции без потери работоспособности решения и стабильности результата.
...
Рейтинг: 0 / 0
20.04.2012, 13:24
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37762909
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
MasterZivКто его банит-то ? Без него скучно будет. :-)

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

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

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

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

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

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

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

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

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

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

Но вы можете за один проход вытянуть список неповторяющихся элементов. Этого достаточно
для работы предикатов DISTINCT и GROUP BY.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
20.04.2012, 13:30
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37762927
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
On 04/20/2012 02:21 PM, Dimitry Sibiryakov wrote:

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

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

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

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

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

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

Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
20.04.2012, 13:33
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37762936
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
> Не во всех местных форумах так либеральны.

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

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

Собственно, правильного ответа, почему создание хеш таблицы не является сортировкой я лично дал здесь - 12440698 .
...
Рейтинг: 0 / 0
20.04.2012, 13:35
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37762940
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
Сергей Арсеньев,

точнее почему может не являться
...
Рейтинг: 0 / 0
20.04.2012, 13:36
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37762941
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
MasterZivсамая быстрая сортировка это
O( N log N )
Что я там говорил про ограничение понятия "сортировка" обменными алгоритмами?.. Правильно,
что кому-то пора перечитать Кнута.

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

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

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

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


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

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

Обычно hash таблицу с указателями на подмножества однохешевых строк создают изначально упорядоченной и никто ее специально не сортирует.
...
Рейтинг: 0 / 0
20.04.2012, 14:08
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763021
sphinx_mv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
sphinx_mv
Участник
MasterZiv
> Чем больше Вы пишете, тем больше я сомневаюсь, что даже в этом узком контексте
> Вы понимаете суть хэш-функций и хэш-таблиц...

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

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

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

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

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

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

Собственно процесс созлдания hash таблицы на этом и закончен. Все что идет потом это уже сортировка с использованием hash таблицы, но к ее созданию отношения не имеющий.
...
Рейтинг: 0 / 0
20.04.2012, 14:13
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763034
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
sphinx_mvАга... Я уже заценил уровень "профессионализма" человека, для которого нормально для хэш-таблицы "на лету" менять хэш-функцию, не осознавая, что для этого нужно строить СОВЕРШЕННО ДРУГУЮ, НОВУЮ хэш-таблицу, и который считает перестройку хэш-таблицы на пару-тройку десятков миллионов элементов - копеечной задачей...


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



 

пожалуй буду валить из этого топика, он станял какихто гуманитариев ...
...
Рейтинг: 0 / 0
20.04.2012, 14:15
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763035
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
Люди предлагаю поднапрячься, еще чуть-чуть и мы переплюнем "Чем MS SQL Server хуже Oracle Database?"
...
Рейтинг: 0 / 0
20.04.2012, 14:15
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763039
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Сергей АрсеньевОбычно hash таблицу с указателями на подмножества однохешевых строк создают изначально
упорядоченной и никто ее специально не сортирует.

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

Плевать, что массив в хэш-таблице изначально упорядочен, речь идёт о куртках, то бишь
данных на входе.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
20.04.2012, 14:16
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763047
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
Кстате да, там подымался вопрос, я за то чтобы за откровенный троллинг гуманитариев банить ...
...
Рейтинг: 0 / 0
20.04.2012, 14:19
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763050
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
BazistDimitry SibiryakovНо вы можете за один проход вытянуть список неповторяющихся элементов. Этого достаточно
для работы предикатов DISTINCT и GROUP BY.


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

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

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

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


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

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

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

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


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

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


Ну да, на графике видно всю силу упорядочиваний коллизий которая отображается на скорости поиска .....
...
Рейтинг: 0 / 0
20.04.2012, 14:41
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763131
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
Bazist Какой именно порядок может гарантировать хештаблица.
Гм. У вас ссылки на множества коллизий организованы массивом или произвольным списком?
...
Рейтинг: 0 / 0
20.04.2012, 14:49
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763133
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Сергей АрсеньевДело в том, что пусть A{ai} исходное множество. На выходе получаем
B{Cj}, где Сj это множество {ai} (подмножество A).

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

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

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

A={ai} - А это множество элементов ai
...
Рейтинг: 0 / 0
20.04.2012, 14:56
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763159
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
Dimitry SibiryakovТ.е. то, что я в этом топике уже полдюжины раз сказал "по неубыванию хэша" тебя не
убедило?.. Хорошо, я не гордый, повторю ещё раз: хэш-таблица гарантирует расположение
элементов множества в порядке неубывания хэша ключей элементов этого множества.


Ну вот, в твоем уравнении хешфункция скрыта в реализации хештаблицы и может быть недетерминирована,
тоесть переменная, получается для клиента элементы в черном ящике неупорядочены, зашифрованы, если хочешь,
недерменированы и ложатся коллизии частенько в несортированые списки ....
...
Рейтинг: 0 / 0
20.04.2012, 14:57
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763160
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
BazistНо у вас все Хештаблицы и все элементы оказались строго упорядочеными почемуто
Где выделенное слово?
...
Рейтинг: 0 / 0
20.04.2012, 14:57
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763168
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
Сергей АрсеньевBazistНо у вас все Хештаблицы и все элементы оказались строго упорядочеными почемуто
Где выделенное слово?

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

Нет дружок, элементы или упорядочены или нет, третьего не дано.
...
Рейтинг: 0 / 0
20.04.2012, 14:59
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763199
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
BazistНет дружок, элементы или упорядочены или нет, третьего не дано.
Утрируете. Строгая сортировка, когда функция назначения порядкового номера элементу множества однозначная, если же порядок элементов в множестве может меняться и при этом множество остается упорядоченным, то это не строгое упорядочивание (но иное и невозможно в случае идентичности элементов множества).
...
Рейтинг: 0 / 0
20.04.2012, 15:09
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763209
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
Сергей АрсеньевBazistНет дружок, элементы или упорядочены или нет, третьего не дано.
Утрируете. Строгая сортировка, когда функция назначения порядкового номера элементу множества однозначная, если же порядок элементов в множестве может меняться и при этом множество остается упорядоченным, то это не строгое упорядочивание (но иное и невозможно в случае идентичности элементов множества).

Списки коллизий забыл...
...
Рейтинг: 0 / 0
20.04.2012, 15:11
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763211
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Сергей АрсеньевA={ai} - А это множество элементов ai

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

Поскольку множество B составлено из уникальных элементов множества A, то таки да: можно
утверждать, что любой элемент множества A является членом множества B.

Но я таки повторю свой вопрос: ответь одним словом: сортируются куртки (то есть входное
множество) при развешивании по крючкам (то есть заполнении хэш-таблицы) или нет? Просто
"да" или "нет".

Bazistв твоем уравнении хешфункция скрыта в реализации хештаблицы и может быть недетерминирована

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


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

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

Вот в этом твое с ними и расхождение - в терминологии.
Ты рассматриваешь B как объединение множеств C, а они как множество множеств.

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

Это я уже понял и даже предложил терминологию согласовать, но их определений так и не увидел.

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

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


Подумай почему в СУБД широко используются сортированные деревья, но нахрен никому не нужен некий "порядок" хештаблицы, который впрочем в неудачных случаях вообще может выродится в тупой фулскан по коллизиям. Наверное потому что пользователи хотят видеть запросы чтото вроде WHERE date between '20120101' and '20120121' на упорядоченных данных, а все что делает хештаблица просто реализовывает свой очень узкоспециализированный алгоритм и достигается он кстате за счет отсудствия строгого порядка в записях.
...
Рейтинг: 0 / 0
20.04.2012, 15:21
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763251
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
BazistПоэтому с точки зрения пользователя чорного ящика под названием "Хеш таблица" ты не знаешь что скрывается под Хешфункцией и какой именно точно хеш будет сгенерирован для твоего ключа. Если честно то написав
Код: javascript
1.
var i = new Array(1024);

я тоже не знаю, на каких физических адресах окажутся элементы массива и будут ли они идти по возрастанию, но полагаю его упорядоченным множеством.
...
Рейтинг: 0 / 0
20.04.2012, 15:24
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763257
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
Сергей АрсеньевBazistПоэтому с точки зрения пользователя чорного ящика под названием "Хеш таблица" ты не знаешь что скрывается под Хешфункцией и какой именно точно хеш будет сгенерирован для твоего ключа. Если честно то написав
Код: javascript
1.
var i = new Array(1024);

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

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

В случае упорядоченности крючков да. Но не строгая. Как заметил Bazist нестрогая за сортировку не катит.
...
Рейтинг: 0 / 0
20.04.2012, 15:28
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763265
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
BazistМассив гарантирует хотябы порядок следования один за одним элемента в адрессном пространстве.
В виртуальном или физическом?
...
Рейтинг: 0 / 0
20.04.2012, 15:29
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763274
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
Сергей АрсеньевBazistМассив гарантирует хотябы порядок следования один за одним элемента в адрессном пространстве.
В виртуальном или физическом?

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

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

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

Не знаю чему вас сейчас в школе учат, но когда меня учили лет десять назад С++, то массив гарантировал что элементы будут в адрессном пространстве рядом. И собственно если менеджеру памяти не удасться выделить запрашиваемый цельный кусок памяти, то он просто пошлет нафиг и вылитит с ошибкой недостаточно памяти.
...
Рейтинг: 0 / 0
20.04.2012, 15:38
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763326
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
BazistНе знаю чему вас сейчас в школе учат, но когда меня учили лет десять назад С++, то массив гарантировал что элементы будут в адрессном пространстве рядом.
"Рядом в адресном пространстве процесса" вовсе не означает "рядом в физической памяти" или даже хотя бы "полностью в физической памяти". Если Вы выделите память под большой массив, и при этом с первой его третью будете работать редко, со второй - часто, а с третьей - вообще не работать, то через какое-то время окажется, что его вторая треть физически находится в кэше процессора, первая треть - не в кэше, но в оперативке, а третья - в свопе.
...
Рейтинг: 0 / 0
20.04.2012, 15:47
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763332
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
softwarerBazistНе знаю чему вас сейчас в школе учат, но когда меня учили лет десять назад С++, то массив гарантировал что элементы будут в адрессном пространстве рядом.
"Рядом в адресном пространстве процесса" вовсе не означает "рядом в физической памяти" или даже хотя бы "полностью в физической памяти". Если Вы выделите память под большой массив, и при этом с первой его третью будете работать редко, со второй - часто, а с третьей - вообще не работать, то через какое-то время окажется, что его вторая треть физически находится в кэше процессора, первая треть - не в кэше, но в оперативке, а третья - в свопе.

вы бы еще назвали что транзисторы не рядом на процессоре блин ....

Короче пойду я от этих зануд.
...
Рейтинг: 0 / 0
20.04.2012, 15:49
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763333
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
BazistНе знаю чему вас сейчас в школе учат, но когда меня учили лет десять назад С++, то массив гарантировал что элементы будут в адрессном пространстве рядом.
"Рядом в адресном пространстве процесса" вовсе не означает "рядом в физической памяти" или даже хотя бы "полностью в физической памяти". Если Вы выделите память под большой массив, и при этом с первой его третью будете работать редко, со второй - часто, а с третьей - вообще не работать, то через какое-то время окажется, что его вторая треть физически находится в кэше процессора, первая треть - не в кэше, но в оперативке, а третья - в свопе.
...
Рейтинг: 0 / 0
20.04.2012, 15:49
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763337
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
Весь топек сплошная подмена понятий какихто ...
Кеши процессора оказались областью памяти "не рядом", хештаблица оказалась с неким порядком, но почемуто нужной только ей для узкоспециализированой задачи ... и т.д.
...
Рейтинг: 0 / 0
20.04.2012, 15:50
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763347
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
Bazistвы бы еще назвали что транзисторы не рядом на процессоре блин ....
Ну если для Вас "рядом" означает "внутри одного системного блока", то не смею задерживать.
...
Рейтинг: 0 / 0
20.04.2012, 15:52
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763357
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
softwarerBazistвы бы еще назвали что транзисторы не рядом на процессоре блин ....
Ну если для Вас "рядом" означает "внутри одного системного блока", то не смею задерживать.

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

"Когда умный показывает пальцем на небо, дурак смотрит на палец"(с)

Вот и им, про адрессную арифметику, а они про кеши процессора

Очень полезная инфа
...
Рейтинг: 0 / 0
20.04.2012, 15:56
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763370
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
> Задача:
> Мальчик Петя дежурит по раздевалке, в которой есть вешалка с крючками,
> подписанными от 1
> до 100. На полу валяется куча курток, на которых пришиты бирки с номерами.
> Мальчик Петя
> берёт куртки из кучи и вешает на крючки с соответствующими номерами.

Аналогия неверная.
Это -- массив.
Хэш-таблица выглядит по-другому:

есть 20 вешалок, на вешалках крючки БЕЗ НОМЕРОВ.
На каждой вешалке можно повесить 40 курток.
На каждой куртке -- класс и имя и фамилия ученика (считаем, что
класс и ФИО уникальны внутри школы).

Приходит ученик, гардеробщик берёт у него куртку и
ученик уходит. Гардеробщик, чтобы не перебирать потом
все 20*40 = 800 крючков, когда надо будет выдать куртку,
ведёт ведомость, на какую вешалку он повесил какую куртку.
(вешалки от 1 до 20). И даже не так, ему ЛЕНЬ вести ведомость,
и он придумал правило -- я возьму номер по порядку буквы алфавита,
с которой начинается имя ученика, вычислю от остаток от деления на 20
(кол-во вешалок) и на эту вешалку буду всегда вешать куртку.

Соотв. приходит ученик за курткой, говорит: "Я-- Вася Иванов,
5Б класс". Гардеробщик -- АГА! "И" - это 10-ая вешалка, пойду
поищу там Иванова Васю из 5-го Б. Идёт, смотрить ВСЕ (!) куртки
на крючках (где, разумеется, есть куртки), и читает бирки,
ищет нужную куртку. Находит -- отдаёт, не находит -- говорит --
"А извини, мальчик, ты мне сегодня куртку не сдавал.".

Вот теперь можно задаваться вопросом, упорядочены ли куртки на вешалках.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
20.04.2012, 15:56
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763371
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
BazistНе знаю чему вас сейчас в школе учат, но когда меня учили лет десять назад С++, то массив гарантировал что элементы будут в адрессном пространстве рядом.
1. пример был не на C++
2. Я уточнил про виртуальное (процесса) или физическое (компьютера) адресное пространство. Ноне оно вообще может оказаться в NUMA архитектуре, что идущие подряд элементы, будут лежать в адресных пространствах разных контроллеров памяти. Жуть. Но представление об системе как о черном ящике жить не мешает.

Резюмирую (на сегодня надоело переливать из пустого в порожнее).
Была задача поиск в 1E6 элементов. Даже простая группировка на тысячу групп по тысяче элементов скороее всего значительно сократит количество переборов при поиске.
Если же данные отсортированны, то поиск можно еще сократить (хоть методом пополамного деления).

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

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

Смею заметить, что другого подобного топика посвященного этому вопросу, где бы апологеты не обливали грязью не их любимые СУБД еще поискать...
...
Рейтинг: 0 / 0
20.04.2012, 15:59
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под 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
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763761
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Сергей АрсеньевТ.е. упорядочивать ключи с одинаковым значением кеша?
А на, тоесть зачем их там упорядочивать? Время тратить.

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

Чтобы поиск среди вышеуказанных Базистом 5000 коллизий был быстрее. Ты согласен, что поиск
в упорядоченном списке быстрее чем в неупорядоченном?


Не будет там списков, просто на некоторые элементы массива будет приходится по 2-3 ключа в среднем.
Тоесть эти 5000 коллизий распределятся на 10 миллионов изспользованых уже ячеек.

А какой толк упорядочивать коллизии на 2-3 элемента ?

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

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

То есть ты выше фигню написал, а я, как дурак, повёлся. Ню-ню...


Где фигня ?
Забаньте его уже ктото за тупосць ...
...
Рейтинг: 0 / 0
20.04.2012, 18:30
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763810
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
BazistГде фигня ?
Вот тут:
BazistУ неудачной хешфункции 1000 неодинаковых элементов-ключей в разнобой окажутся
в одной ячейке
BazistНа 25 миллионов элементов, количество коллизий составило 1 миллион 321
тысяча.
Ты бы уж определился бы...
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
20.04.2012, 18:38
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763813
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
Dimitry Sibiryakov,

Ты слово неудачная прочитал ?
...
Рейтинг: 0 / 0
20.04.2012, 18:39
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763818
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
BazistТы слово неудачная прочитал ?
А в коде ты, конечно, использовал удачную. Тогда вопрос на засыпку: зачем ты наваял
неудачную, когда мог сразу использвоать удачную?
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
20.04.2012, 18:43
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763824
sphinx_mv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
sphinx_mv
Участник
BazistDimitry Sibiryakov,

Ты слово неудачная прочитал ?
Использовать "удачную" Вам не позволяют религиозные убеждения?
...
Рейтинг: 0 / 0
20.04.2012, 18:44
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763829
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
> list.Add(i.ToString().GetHashCode(),0);

> Вот, ради интереса.
> Свыше 5000 коллизий

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


Ты паскаль в школе учил хоть, ну хоть когдато ?
...
Рейтинг: 0 / 0
20.04.2012, 18:47
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763835
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
sphinx_mvBazistDimitry Sibiryakov,

Ты слово неудачная прочитал ?
Использовать "удачную" Вам не позволяют религиозные убеждения?

Еще один ...
Хешфункция которая уже на 25 миллионах элементов генерит каждый 25й раз коллизию,
хотя остальных все еще свободных ячеек 4 миллиарда 175 миллионов еще свободны, удачная или неудачная ?
...
Рейтинг: 0 / 0
20.04.2012, 18:49
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763837
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
Ладно, для ________ повторяю еще раз. (
Нет удачных или неудачных хешфункций.
Хешфункций несчетное количество на свете и отличают их все то, что одни типы ключей они хорошо равномерно распределяют, другие нет. Точка.
...
Рейтинг: 0 / 0
20.04.2012, 18:51
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763843
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
MasterZiv
> list.Add(i.ToString().GetHashCode(),0);

> Вот, ради интереса.
> Свыше 5000 коллизий

Справедливости ради, нужно отметить, что
i.ToString().GetHashCode() -- это не вся хэш-функция, это только
её часть. Реальная хэш-функция представляет собой ещё некие
манипуляции над результатом этой фунции ( GetHashCode() ).


Это уже по барабану.
Если GetHashCode() вернул для двух разных ключей одно и тоже, то
как не танцуй любая детерменированая новая хешфункция вернет тотже самый результат.
...
Рейтинг: 0 / 0
20.04.2012, 18:58
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763847
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
MasterZiv,

Скорей всего хештаблица не может выделить сразу массив на 4 миллиарда ячеек * 4 байта инта,
поэтому както его преобразовывает в двухбайтный хеш, например, чтобы выделять только 65 кб * 4 байта "упорядоченой" памяти.
Тоесть фактически коллизий будет намного больше.
...
Рейтинг: 0 / 0
20.04.2012, 19:01
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763860
sphinx_mv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
sphinx_mv
Участник
BazistЛадно, для ________ повторяю еще раз. (
Нет удачных или неудачных хешфункций.
Хешфункций несчетное количество на свете и отличают их все то, что одни типы ключей они хорошо равномерно распределяют, другие нет. Точка.
Склероз крепчал...
То есть, это не Вы тут растекались мыслями по древу на тему "удачности" и "неудачности" хэш-функций?
...
Рейтинг: 0 / 0
20.04.2012, 19:11
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763866
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
sphinx_mvBazistЛадно, для ________ повторяю еще раз. (
Нет удачных или неудачных хешфункций.
Хешфункций несчетное количество на свете и отличают их все то, что одни типы ключей они хорошо равномерно распределяют, другие нет. Точка.
Склероз крепчал...
То есть, это не Вы тут растекались мыслями по древу на тему "удачности" и "неудачности" хэш-функций?

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

О, дайте, дайте мне неудачный набор данных для md5. Я поломаю все линуксы в округе,
которые наивно используют её для паролей.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
20.04.2012, 20:05
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763933
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
могу тебе дать только два крючка
повесишь в школьной раздевалке
отсортированные кеды.
Справишся ?
...
Рейтинг: 0 / 0
20.04.2012, 20:33
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37763946
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
> Скорей всего хештаблица не может выделить сразу массив на 4 миллиарда ячеек * 4
> байта инта,
> поэтому както его преобразовывает в двухбайтный хеш, например, чтобы выделять
> только 65 кб * 4 байта "упорядоченой" памяти.

Конечно.

> Тоесть фактически коллизий будет намного больше.

Конечно.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
20.04.2012, 20:55
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37764498
sphinx_mv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
sphinx_mv
Участник
Bazistsphinx_mvпропущено...

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

Склероз какбы еще хорошо, означает что когдато эти знания хоть там были ... а здесь...

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

Для склеротиков напоминаю их слова - не бывает удачных и неудачных хэш-функций.
От себя добавлю, что точно так же не бывает удачных и неудачных данных: данные в реальном мире НЕ ПОДБИРАЮТ, а используют, те что есть...
Ну, а если кто-то не умеет правильно выбирать хэш-функции и работать с ними с учетом возможных коллизий...

BazistИ наоборот, зная весь набор ключей можно подобрать такую хешфункцию которая вообще не даст коллизий. Рехешировании которое вам уже целый день вдалбливают.
Для особо "сообразительных" рассказываю: математика утверждает, что НЕ СУЩЕСТВУЕТ хэш-функций БЕЗ коллизий. То есть - ВООБЩЕ .
Соответственно, перевыборы другой хэш-функции и перехэширование наборов данных - занятие для интеллектуальных онанистов.
...
Рейтинг: 0 / 0
21.04.2012, 16:25
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37764501
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
sphinx_mv математика утверждает, что НЕ СУЩЕСТВУЕТ хэш-функций БЕЗ коллизий. То есть - ВООБЩЕ .
Выбросьте такую математику и возьмите ту, которая работает.
...
Рейтинг: 0 / 0
21.04.2012, 16:28
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37764574
Фотография SergSuper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SergSuper
Участник
sphinx_mv,

Вы искренне считаете что употребление терминов "склеротики", "интеллектуальные онанисты" делает высказывание убедительнее?
...
Рейтинг: 0 / 0
21.04.2012, 18:06
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37764617
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
sphinx_mv,

Можно вас попросить огласить возраст должность и опыт работы ?
Поймите правильно, тратишь тратишь свое время а в итоге на том конце какойто 14ти летний
ученик кулинарного училища решил за мой
счет скилы свои прокачивать.
Просто по третьему кругу я ничего обьяснять не буду пока не пойму кто передо мной
...
Рейтинг: 0 / 0
21.04.2012, 18:50
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37764738
Фотография SergSuper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SergSuper
Участник
Bazistsphinx_mv,

Можно вас попросить огласить возраст должность и опыт работы ?прежде чем такое спрашивать в приличном обществе оглашают свой
...
Рейтинг: 0 / 0
21.04.2012, 21:27
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37764739
sphinx_mv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
sphinx_mv
Участник
softwarersphinx_mv математика утверждает, что НЕ СУЩЕСТВУЕТ хэш-функций БЕЗ коллизий. То есть - ВООБЩЕ .
Выбросьте такую математику и возьмите ту, которая работает.
Wang Xiaoyun; Lai Xuejia; Yu Hongbo; Marc Stevens; Jacob Appelbaum; Christophe De Cannière...
Им тоже предложите?
...
Рейтинг: 0 / 0
21.04.2012, 21:28
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37764751
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
SergSuperBazistsphinx_mv,

Можно вас попросить огласить возраст должность и опыт работы ?прежде чем такое спрашивать в приличном обществе оглашают свой

Уже писал
10 лет опыта в программировании
и полтора года плотно курю хештаблы.
Теперь свой огласите. С удовольствием пообщаюсь в топике с челом у кого можно
что нового узнать, для остальных репетиторы
дело не бесплатное
...
Рейтинг: 0 / 0
21.04.2012, 21:47
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37764752
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
sphinx_mvWang Xiaoyun; Lai Xuejia; Yu Hongbo; Marc Stevens; Jacob Appelbaum; Christophe De Cannière...
Им тоже предложите?
Зависит от того, понимают ли они, что пишут, и способны ли корректно это сформулировать. Я не знаю этих людей и не могу сказать, следуют ли они Вашей практике противоречить самому себе.
...
Рейтинг: 0 / 0
21.04.2012, 21:49
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37764755
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
sphinx_mvsoftwarerпропущено...

Выбросьте такую математику и возьмите ту, которая работает.
Wang Xiaoyun; Lai Xuejia; Yu Hongbo; Marc Stevens; Jacob Appelbaum; Christophe De Cannière...
Им тоже предложите?

Я знаю ушу кунгфу дзюдо тейквандо .... и еще много страшных слов (с) Старый анек
...
Рейтинг: 0 / 0
21.04.2012, 21:52
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37764759
sphinx_mv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
sphinx_mv
Участник
Bazistsphinx_mv,

Можно вас попросить огласить возраст должность и опыт работы ?

Чтобы мне понять, что кое-кто "не в курсе предмета", и первое, и второе вполне достаточны...
Для получения этой информации в "развернутом" виде Вам еще "качаться" и "качаться"..."
BazistПоймите правильно, тратишь тратишь свое время а в итоге на том конце какойто 14ти летний
ученик кулинарного училища решил за мой
счет скилы свои прокачивать.

Вы только что озвучили свой уровень - даже "кулинарщик" на Вас может "прокачаться"...
Счастье, что я не на Вашем месте - мне было бы стыдно...
BazistПросто по третьему кругу я ничего обьяснять не буду пока не пойму кто передо мной
Если нет другого способа заставить Вас прекратить пороть чушь - не дождетесь...
...
Рейтинг: 0 / 0
21.04.2012, 21:55
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37764761
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
sphinx_mv,

Обычные цифры звучали бы красноречивей...
...
Рейтинг: 0 / 0
21.04.2012, 21:59
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37764762
Фотография SergSuper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SergSuper
Участник
BazistТеперь свой огласите. С удовольствием пообщаюсь в топике с челом у кого можно
что нового узнать, для остальных репетиторы
дело не бесплатноене буду (собственно я у Вас и не спрашивал), но в любом случае он гораздо больше
я тут как бы ничего не пытаюсь доказать и делаю замечания на правах модератора, хочется чтобы обсуждали технологии, а не у кого длиннее

так же пользуясь случаем хотел бы попросить Вас заменить в профиле пункт "Откуда", т.к. считаю его неприличным, что является основанием для бана
...
Рейтинг: 0 / 0
21.04.2012, 22:01
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37764763
sphinx_mv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
sphinx_mv
Участник
softwarersphinx_mvWang Xiaoyun; Lai Xuejia; Yu Hongbo; Marc Stevens; Jacob Appelbaum; Christophe De Cannière...
Им тоже предложите?
Зависит от того, понимают ли они, что пишут, и способны ли корректно это сформулировать. Я не знаю этих людей и не могу сказать, следуют ли они Вашей практике противоречить самому себе.
Воспользуйтесь гуглем по любому из списка...
И после этого попробуйте ЕЩЕ раз найти противоречие в фразе "математика утверждает, что не существует хэш-функций без коллизий".
...
Рейтинг: 0 / 0
21.04.2012, 22:01
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37764764
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
Пока что тяните только на малолетнее хамло такоеже смешное как в озвученом старом анеке :)
...
Рейтинг: 0 / 0
21.04.2012, 22:02
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37764766
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
SergSuper,

Ну по теме я уже страниц пять общался.
Просто раз поправил бред второй третий
а в четвертый раз подумал а зачем я комуто
чтото доказываю в 80% заходит и хамит
молодежь в надежде получить правильные
знания а главное разьяснения на те вещи которые им лень прочитать в учебниках :)
Ну тоесть мне неинтересно
...
Рейтинг: 0 / 0
21.04.2012, 22:08
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37764767
Фотография SergSuper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SergSuper
Участник
Bazist,

на мой взгляд хамство идет как раз от Вас
...
Рейтинг: 0 / 0
21.04.2012, 22:13
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37764769
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
ну нивапрос цифры мне всеравно не назвали
впрочем ожидаемо, поэтому просто удалюсь
из топика чтобы вам лишний раз глаз не мулять :)
...
Рейтинг: 0 / 0
21.04.2012, 22:18
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37764772
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Bazistудалюсь из топика
Так, молодняк, наконец-то, слился.

Теперь, softwarer , давай, рассказывай, что там у тебя за альтернативная математика,
в которой есть хэш-функции без коллизий? Надеюсь, ты не имеешь в виду функцию типа f(x)=x...
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
21.04.2012, 22:23
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37764774
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
sphinx_mvИ после этого попробуйте ЕЩЕ раз найти противоречие в фразе "математика утверждает, что не существует хэш-функций без коллизий".
В этой фразе нет противоречий, она просто очевидно не соответствует истине, поскольку любой школьник в состоянии привести контрпример.
...
Рейтинг: 0 / 0
21.04.2012, 22:23
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37764776
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
Dimitry SibiryakovТеперь, softwarer , давай, рассказывай, что там у тебя за альтернативная математика,
в которой есть хэш-функции без коллизий? Надеюсь, ты не имеешь в виду функцию типа f(x)=x...
Именно её и имею как тривиальный контрпример, хотя, безусловно, несложно построить и другие. Наш скромный инкогнито пару страниц назад писал про хэш-функции upper и lower, так что и тривиальная функция очевидно входит в область определения его понятия "хэш-функции".
...
Рейтинг: 0 / 0
21.04.2012, 22:26
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37764789
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
softwarerИменно её и имею как тривиальный контрпример, хотя, безусловно, несложно построить и другие.

Эх, а я уж было обрадовался...

Но, с узкой точки зрения криптографических хэшей, такую функцию всё-таки нельзя признать
хэш-функцией, поскольку она обратима. Опять же пространство её результатов не меньше
пространства аргументов... Именно этими аргументами меня пытались задавить в этом же
разделе пару лет назад.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
21.04.2012, 22:39
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37764790
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
On 04/21/2012 07:50 PM, Bazist wrote:

Мне кажется, что и когда поймёшь -- не стоит уже.
В смысле -- и так уже понятно, с кем имеешь дело.

На самом деле и объяснять-то ничего не надо -- всё уже написано:

http://en.wikipedia.org/wiki/Hash_table

И даже по русски, :

http://ru.wikipedia.org/wiki/%D0%A5%D1%8D%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0

хотя русскоязычная статья местами безграмотна и неполна.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
21.04.2012, 22:42
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37764794
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
> на мой взгляд хамство идет как раз от Вас

ГДЕ ?
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
21.04.2012, 22:47
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37764808
Bazist
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bazist
Участник
Dimitry Sibiryakov,

А если хеш функция на 100 байт зипует ключ и добавляет один байт
муссора для необратимости и возвращает 20 байт хеша, работает без коллизий, это не хешфункция ?
...
Рейтинг: 0 / 0
21.04.2012, 23:01
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37764826
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
О, юное дарование с целыми десятью годами опыта программирования вернулось... Так он ещё и
обманщик ко всему... Да ещё и с вопросом, заставляющим задуматься чем же он полтора года с
хэш-функциями занимался.
BazistА если хеш функция на 100 байт зипует ключ и добавляет один байт
муссора для необратимости и возвращает 20 байт хеша, работает без коллизий, это не
хешфункция ?

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

решил опять мне хамить ?

А между тем существует куча способов
сделать функцию необратимой
и на понятие хеш функция это не влияет.
Это опять выдуманое требование неучи
такоеже как сортировки в хештаблицах
...
Рейтинг: 0 / 0
21.04.2012, 23:26
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37764843
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Bazistрешил опять мне хамить ?

Мужик сказал - мужик сделал! Ты сказал, что уходишь, но остался.

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

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

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

С чего бы этот ушедший представитель поколения пепси решил, что выравнивание -
необратимо?.. Наверное, педовикий каких-нибудь начитался... Это явный случай диагноза
"смотрит в книгу, видит фигу".
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
21.04.2012, 23:56
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37764858
Фотография SergSuper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SergSuper
Участник
Dimitry SibiryakovBazistМуссором может быть и определенное выравнивание байт, которое вносит необратимость но не
вносит коллизий и оставляет детерминированость.

С чего бы этот ушедший представитель поколения пепси решил, что выравнивание -
необратимо?.. Наверное, педовикий каких-нибудь начитался... Это явный случай диагноза
"смотрит в книгу, видит фигу".можно было его еще попросить написать функцию, которая гарантированно 100 байт в 20 пакует
...
Рейтинг: 0 / 0
22.04.2012, 00:13
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37764878
Учитель информатики
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Учитель информатики
Гость
Вроде давно говорили
о природе ключей и эффективной хешфункции.
Если все ключи это текст за основой 26 то хешкод за основой 256 даст неплохое сжатие.
Выравнивание байт также как округление может быть необратимо.
P.S.
Но это как я понял
...
Рейтинг: 0 / 0
22.04.2012, 00:45
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37764880
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
SergSuperможно было его еще попросить написать функцию, которая гарантированно 100 байт в 20 пакует

Ну, от этого ему было бы слишком просто увернуться: "написал суперархиватор - любой файл
сжимает до одного байта, теперь думаю над распаковкой". Он отмазался бы не глядя: "просили
же необратимую". А может и не отмазался бы... ФИДОшной закалки в области флейма всё же у
него нету... Что с них возьмёшь, молодых-зелёных...
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
22.04.2012, 00:46
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37765711
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
Люди, ваш спор мне напомнил один анекдот, про математика, гордо заявившего, что универсального архиватора не существует и объявившего премию за то, что кто-то напишет архиватор, который обратимо сожмет любой файл хотя бы на 1 байт. Ну и про программиста, который этот архиватор написал.
...
Рейтинг: 0 / 0
23.04.2012, 09:35
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37765889
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
> Люди, ваш спор мне напомнил один анекдот, про математика, гордо заявившего, что
> универсального архиватора не существует и объявившего премию за то, что кто-то
> напишет архиватор, который обратимо сожмет любой файл хотя бы на 1 байт. Ну и
> про программиста, который этот архиватор написал.

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

Не до одного байта, а хотя бы на один байт. :)
А к топику не имеет отношения ~99% постов в этом треде.

MasterZiv,
Так фраза про "математика утверждает," навеяло. Ну и спор яляется ли f(x)=x хеш функцией.
...
Рейтинг: 0 / 0
23.04.2012, 13:53
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37766231
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Сергей АрсеньевНе до одного байта, а хотя бы на один байт. :)

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

В анекдоте был ньюанс. :)
...
Рейтинг: 0 / 0
23.04.2012, 14:34
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37772999
АнатоЛой
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
АнатоЛой
Участник
Сергей АрсеньевDimitry Sibiryakov,

В анекдоте был ньюанс. :)
Либо анекдот не знаю, либо ты его привёл не так, либо я под конец дня туплю...

В чём нюанс, в слове "любой", что-ли?

Если "любой" = "для всех файлов, которые можно подсунуть архиватору, он обратимо сожмёт этот файл хотя бы на один байт", то:

1) смотри комментарий Dimitry Sibiryakov - значит такой архиватор может сжать любой файл после многократного применения до одного байта.

2) файл размер в один байт чудо архиватор сжимает в 0 байт?

Если "любой" = "это какой-то файл, который программист выберет и подсунет архиватору" - то да, программист молодец.
...
Рейтинг: 0 / 0
26.04.2012, 19:45
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37773169
Фотография SergSuper
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SergSuper
Участник
АнатоЛойСергей АрсеньевDimitry Sibiryakov,

В анекдоте был ньюанс. :)
Либо анекдот не знаю, либо ты его привёл не так, либо я под конец дня туплю...

В чём нюанс, в слове "любой", что-ли?

Если "любой" = "для всех файлов, которые можно подсунуть архиватору, он обратимо сожмёт этот файл хотя бы на один байт", то:

1) смотри комментарий Dimitry Sibiryakov - значит такой архиватор может сжать любой файл после многократного применения до одного байта.

2) файл размер в один байт чудо архиватор сжимает в 0 байт?

Если "любой" = "это какой-то файл, который программист выберет и подсунет архиватору" - то да, программист молодец.

Там был не анекдот, а реальная история о там как поспорили два програмиста (назовем "математик"(М) и "программист"(П))
М сказал что невозможно написать такой архиватор, который будет гарантированно сжимать любой файл и обещал $500(с суммой, как и с другими деталями, возможно я вру) если кто сможет сжать то, что он нагенерит, причем сам распаковщик должен включаться в сжимаемое
тогда П спросил: а результат сжатия может быть в нескольких файлах или обязательно в одном?
М ответил что может быть в нескольких
также П сказал что ему нужен файл объема не меньше какого-то (довольно приличного)
М согласился и прислал файл

в ответ П прислал несколько файлов(вроде как несколько сотен), которые в сумме по размеру вместе с распаковщиком были чуть меньше первоначального


М очень долго препирался, но потом заплатил


если непонятно как было запаковано, то реализация примерно такая:
выбирался какой-то символ(допустим пробел)
вырезался кусок от начала до первого пробела и записывался в файл под номером 1
далее тоже самое делалось со вторым куском и соответственно записывалось под номером 2
т.е. общий размер файлов отличался на количество пробелов
ну и распаковщик не особо сложно было сделать на ассемблере


но вообще это история тут на мой взгляд никаким боком

а еще есть анекдот как сжать любой файл до нужного размера:
сжимаем файл зипом
если размер больше чем нужно - переименовываем расширение с zip на txt
сжимаем заново
повторяем пока не получится нужный размер
...
Рейтинг: 0 / 0
26.04.2012, 23:55
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37774202
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сергей Арсеньев
Участник
SergSuper,

Гм. Не этот анекдот.

АнатоЛой ,
да файл в 1 байт сжмался в файл длинной 0 байт (ноль по условиям задачи сжимать не надо было). Других файлов задействовано не быо. Файл можно было переносить на другой компьютер и он расжимался.
...
Рейтинг: 0 / 0
27.04.2012, 14:05
| Ответить | Цитировать | Написать  
СУБД для временного хранения данных из бинарного файла (под Delphi).
    #37774552
АнатоЛой
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
АнатоЛой
Участник
Сергей Арсеньев, ну тогда всё понятно: отрезаем байт от файла, значение этого байта в 16-ричном формате приписываем к названию файла, даём расширение "*.loy". Вуаля. Оно? :)
...
Рейтинг: 0 / 0
27.04.2012, 16:01
| Ответить | Цитировать | Написать  
311 сообщений из 311, показаны все 13 страниц
  все  
Форумы / Сравнение СУБД [игнор отключен] [закрыт для гостей] / СУБД для временного хранения данных из бинарного файла (под Delphi).
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?all=1&fid=35&tid=1552562]:
 0ms
get settings:
 10ms
get forum list:
 13ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 33ms
get topic data:
 12ms
get forum data:
 3ms
get page messages:
 267ms
get tp. blocked users:
 1ms
others: 228ms
total:  575ms
созд. / загр.: 575ms
x
x
Закрыть


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