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

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

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


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

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

Сергей Арсеньев
A={ai} - А это множество элементов ai

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

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

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

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

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

Posted via ActualForum NNTP Server 1.5

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

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


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

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

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

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

Posted via ActualForum NNTP Server 1.5

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

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

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

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

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

Сергей Арсеньев
Вот в этом твое с ними и расхождение - в терминологии.

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

Таки ответь: развешивание по крючкам это сортировка или нет?

Posted via ActualForum NNTP Server 1.5

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

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

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


Подумай почему в СУБД широко используются сортированные деревья, но нахрен никому не нужен некий "порядок" хештаблицы, который впрочем в неудачных случаях вообще может выродится в тупой фулскан по коллизиям. Наверное потому что пользователи хотят видеть запросы чтото вроде WHERE date between '20120101' and '20120121' на упорядоченных данных, а все что делает хештаблица просто реализовывает свой очень узкоспециализированный алгоритм и достигается он кстате за счет отсудствия строгого порядка в записях.
20 апр 12, 15:21    [12446439]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
Сергей Арсеньев
Member

Откуда:
Сообщений: 4118
Bazist
Поэтому с точки зрения пользователя чорного ящика под названием "Хеш таблица" ты не знаешь что скрывается под Хешфункцией и какой именно точно хеш будет сгенерирован для твоего ключа.
Если честно то написав
var i = new Array(1024);
я тоже не знаю, на каких физических адресах окажутся элементы массива и будут ли они идти по возрастанию, но полагаю его упорядоченным множеством.
20 апр 12, 15:24    [12446471]     Ответить | Цитировать Сообщить модератору
 Re: СУБД для временного хранения данных из бинарного файла (под Delphi).  [new]
Bazist
Member [заблокирован]

Откуда: Спілкуйся Українською
Сообщений: 8157
Блог
Сергей Арсеньев
Bazist
Поэтому с точки зрения пользователя чорного ящика под названием "Хеш таблица" ты не знаешь что скрывается под Хешфункцией и какой именно точно хеш будет сгенерирован для твоего ключа.
Если честно то написав
var i = new Array(1024);
я тоже не знаю, на каких физических адресах окажутся элементы массива и будут ли они идти по возрастанию, но полагаю его упорядоченным множеством.


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

Откуда:
Сообщений: 4118
Dimitry Sibiryakov
Таки ответь: развешивание по крючкам это сортировка или нет?

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

Откуда:
Сообщений: 4118
Bazist
Массив гарантирует хотябы порядок следования один за одним элемента в адрессном пространстве.

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

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

В виртуальном или физическом?


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

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

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

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

Откуда: Спілкуйся Українською
Сообщений: 8157
Блог
Сергей Арсеньев
Bazist
физическом. По индексу всегда можно забрать элемент.

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

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


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

Откуда: 127.0.0.1
Сообщений: 67477
Блог
Bazist
Не знаю чему вас сейчас в школе учат, но когда меня учили лет десять назад С++, то массив гарантировал что элементы будут в адрессном пространстве рядом.

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

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

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


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

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

Откуда: 127.0.0.1
Сообщений: 67477
Блог
Bazist
Не знаю чему вас сейчас в школе учат, но когда меня учили лет десять назад С++, то массив гарантировал что элементы будут в адрессном пространстве рядом.

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

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

Откуда: 127.0.0.1
Сообщений: 67477
Блог
Bazist
вы бы еще назвали что транзисторы не рядом на процессоре блин ....

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

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

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


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

Откуда: Спілкуйся Українською
Сообщений: 8157
Блог
Но как говорил Энштейн,

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

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

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

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


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

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

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

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

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

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

Posted via ActualForum NNTP Server 1.5

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

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

1. пример был не на C++
2. Я уточнил про виртуальное (процесса) или физическое (компьютера) адресное пространство. Ноне оно вообще может оказаться в NUMA архитектуре, что идущие подряд элементы, будут лежать в адресных пространствах разных контроллеров памяти. Жуть. Но представление об системе как о черном ящике жить не мешает.

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

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

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


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

Я тебе потом расскажу про рехэширование, на том же примере свешалками, если сам
не дойдёшь.

Posted via ActualForum NNTP Server 1.5

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

Откуда:
Сообщений: 4118
Bazist
Весь топек сплошная подмена понятий какихто ...

Вы не поверите, начиналось все с любимого холиварного вопроса - какую БД выбрать.

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