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

Откуда: Новоукраинск
Сообщений: 16864
Дмитрий , поздравляю вы на границе открытия , над которым ученные мужи ломают мозги уже десятки лет.


Dimitry Sibiryakov

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



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


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


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

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

ДохтаР
Единственное осталось , избавить вашу теорию от взаимоисключающих параграфов.

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

Posted via ActualForum NNTP Server 1.5

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

Откуда: Новоукраинск
Сообщений: 16864
Dimitry Sibiryakov
ДохтаР
Единственное осталось , избавить вашу теорию от взаимоисключающих параграфов.

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


Еще раз :

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


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

Ваши функции туда попадают чуть более более чем со 100% вероятностью )
19 апр 12, 15:03    [12439893]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
MasterZiv
Member

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

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

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

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

On 04/19/2012 03:41 PM, Dimitry Sibiryakov wrote:

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

В его содержании, естественно :-)
Это утверждение ложно.

Posted via ActualForum NNTP Server 1.5

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

Откуда: 127.0.0.1
Сообщений: 67383
Блог
Сергей Арсеньев
Под сортировкой можно подразумевать получение из неупорядоченного (произвольного) множества упорядочного.

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

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

Откуда:
Сообщений: 4118
Freimaks
В качестве ключа я попытался использовать MD5, которая считается для строки X+Y+Z+Time.

Тыб еще SHA1024 взял. Тебе не надо обратной невосстановимости, тебе скорость нужна. Возми чего попроще (хоть CRC или последовательный XOR байтов).
Ну и по хешу надо запоминать список вариантов значений полей ему уодвлетворяющий.

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

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

On 04/19/2012 03:43 PM, Freimaks wrote:

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

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

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

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

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

Posted via ActualForum NNTP Server 1.5

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

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

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

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

Откуда:
Сообщений: 51
Щас переделал так:
В Type прописал новый объект TPair, состоящий из 4 полей (X,Y,Z,Time). Завел переменную Pair:TPair;
Далее при чтении файла заполняются эти 4 поля и в TDictionary используются как ключ в виде переменной Pair. Но памяти жрет опять же немерено - на файл в 126 Мб, отъедается около 400 Мб.
19 апр 12, 15:18    [12440030]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
MasterZiv
Member

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


> Тыб еще SHA1024 взял. Тебе не надо обратной невосстановимости, тебе скорость
> нужна. Возми чего попроще (хоть CRC или последовательный XOR байтов).
> Ну и по хешу надо запоминать список вариантов значений полей ему уодвлетворяющий.

Блин, ещё один. Ему надо дубликаты искать, ему нельзя никакие свёртки
использовать. Надо сами значения уникальных полей.

Posted via ActualForum NNTP Server 1.5

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

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



> В Type прописал новый объект TPair, состоящий из 4 полей (X,Y,Z,Time).

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

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

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

Posted via ActualForum NNTP Server 1.5

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

Откуда:
Сообщений: 4118
softwarer
Не просто "упорядоченного", а "упорядоченного по некоему заранее заданному критерию".

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

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

Дискутировать на эту тему можно долго. И безпонтово. Как и о том, что эффективнее дерево или hash таблица. Первое сложно строить - второе может быть неэффективно на конкретных данных.
19 апр 12, 15:23    [12440094]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
Freimaks
Member

Откуда:
Сообщений: 51
MasterZiv
> В Type прописал новый объект TPair, состоящий из 4 полей (X,Y,Z,Time).
Да, похоже маразм -- это заразное... (чур меня, чур).
> Далее при чтении файла заполняются эти 4 поля и в TDictionary используются как
> ключ в виде переменной Pair. Но памяти жрет опять же немерено - на файл в 126
> Мб, отъедается около 400 Мб.

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

Сори, если что-то пропустил - уже столько всего тут написали. А как еще действовать если не так???
Т.е. грубо говоря - этот инструмент сам удаляет дубликаты, наличие дубликатов определяется по одинаковому ключу, соответственно этот ключ надо как-то сформировать. Единственное что мне пришло в голову - считать сумму, но подсказали по поводу пар - я переделал на пары... работает пошустрее конечно, но не идеально, кто же спорит.
19 апр 12, 15:25    [12440110]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
Dimitry Sibiryakov
Member

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

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

Но привести доказательство его ложности Вы, конечно же, откажетесь...

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

Дмитрий же делает вид, что сортировкой является упорядочивание по некоему случайному
критерию, определяемому в процессе собственно упорядочивания.

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

Posted via ActualForum NNTP Server 1.5

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

Откуда:
Сообщений: 4118
Freimaks
А как еще действовать если не так???

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

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

Но привести доказательство его ложности Вы, конечно же, откажетесь...

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

Дмитрий же делает вид, что сортировкой является упорядочивание по некоему случайному
критерию, определяемому в процессе собственно упорядочивания.

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


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

Поэтому хеш от 1 может быть 45456456, а от 1000000000 может быть 54,
никаких требований "для сортировки" у хешфункции нет и быть не может.
19 апр 12, 16:11    [12440595]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
softwarer
Member

Откуда: 127.0.0.1
Сообщений: 67383
Блог
Сергей Арсеньев
Хотелось бы пояснить, чем просто "упорядоченного" отличается от "упорядоченного по некоему заранее заданному критерию" и возможно ли первое без второго?

Конечно, возможно. Представьте себе, например, что мы вставили в некую таблицу 100 записей и затем выбираем их select-ом. Мы увидим их в каком-то порядке, но отсортирована ли выборка?

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

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

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

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

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

softwarer
Представьте себе, например, что мы вставили в некую таблицу 100 записей и затем выбираем
их select-ом. Мы увидим их в каком-то порядке, но отсортирована ли выборка?

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

Posted via ActualForum NNTP Server 1.5

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

Откуда:
Сообщений: 4118
softwarer
Мы увидим их в каком-то порядке, но отсортирована ли выборка?

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

Откуда:
Сообщений: 4118
Dimitry Sibiryakov
rownum в ней монотонно возрастает, нет?..

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

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

Сергей Арсеньев
отсортированный, это не тот который в определенном порядке, это тот, который отсортировали.

<sarkazm on>Вы ещё добавьте "методом пузырька"...<sarkazm off>
Зачем такие ограничения на процесс? Главное - результат.

Posted via ActualForum NNTP Server 1.5

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

Откуда:
Сообщений: 51
Сергей Арсеньев
Freimaks
А как еще действовать если не так???

Вы пробовали построить массив массивов или нет?

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

Откуда: 127.0.0.1
Сообщений: 67383
Блог
Dimitry Sibiryakov
Э-э-э... Александр, Вы хэш-функцию считаете "случайным критерием"?

Да, безусловно.

Dimitry Sibiryakov
Утверждаете её недетерминированность?

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

Dimitry Sibiryakov
Или на каком ещё основании Вы утверждаете,

На том основании, что когда я смотрю на данные, например

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
  • Ваша реализация выдержит замену хэш-таблицы на другую с тем же интерфейсом и другой реализацией

    Вы убедительно докажете, что хэширование является сортировкой. Поскольку это Вам не под силу - я имею полное основание утверждать, что Вы в очередной раз занимаетесь безответственным словоплётством.
  • 19 апр 12, 16:34    [12440833]     Ответить | Цитировать Сообщить модератору
    Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 [4] 5 6 7 8 9 10 .. 13   вперед  Ctrl
    Все форумы / Сравнение СУБД Ответить