Я не понял, как оно обеспечит O(1)? Оно всегда хранит в памяти инфу, позволяющую получить конкретное смещение страницы в неком файле?

Любое key-value это отображение хешей в индексы. В реальности массив с индексом хеш и значением индекс записи, либо индекс самого значения. O(хоть сколько) не имеет никакого отношение к тому где, что и как оно хранит.

Для обеспечения O(1) нам надо просто иметь динамический массивчик. При этом из этого не следует никак то, что за массивчиком у нас ничего нет. Там может быть хоть поиск перебором по 1кк елементам. Главное отвязать это от n. Это делается просто - я уже показал как. К n мы привязывает длину массива.

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

Ну, не любое. Ключи можно хранить и не хешируя. Зачем их хешировать, если полный ключ всё равно надо где-то хранить? Дешевле хранить только полный ключ.

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

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

Какое-то лажовое мнение. Написать O(1) про дисковую БД - это сообщить вполне конкретную вещь, что у нас будет в худшем случае только 1 доступ к диску, 1 seek в худшем случае. Это вполне конкретная информация и на разводилово никак не тянет. Зачем в таких высерах автор бы кого-то разводил, ведь могут запустить тесты и узнать что он олень?

Это делается просто - я уже показал как. К n мы привязывает длину массива.

Лажу ты какую-то высрал, если чесна.

В тему врываются эксперты.

Ну, не любое. Ключи можно хранить и не хешируя. Зачем их хешировать, если полный ключ всё равно надо где-то хранить? Дешевле хранить только полный ключ.

Чего хешировать и причём тут ключи? Не разбираешься в теме - проходи мимо. Иди загугли зачем и причём тут хеши.

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

Я не буду ничего говорить о твоём уровне развития, но всё же. Я тебе удивлю, но в моём описании ровно один «дисковы сик». Он происходит на этапе доступа к элементу массива. А уж сколько этот весит этот елемент - мегабайт, либо гигабайт ничего не меняет, ибо в любом случае будет O(1).

Да и вообще. Своим «обычно» можешь подтереться. В цитате я этого не вижу. Либо пруфцуй, либо не болтай.

Какое-то лажовое мнение. Написать O(1) про дисковую БД - это сообщить вполне конкретную вещь, что у нас будет в худшем случае только 1 доступ к диску, 1 seek в худшем случае. Это вполне конкретная информация и на разводилово никак не тянет. Зачем в таких высерах автор бы кого-то разводил, ведь могут запустить тесты и узнать что он олень?

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

Производительность определяется не только сиками, но и трупутом. Ты, пока только в своих фантазиях, определил, что кол-во сиков от n не зависит. Но ты не определил зависимость роста трупута от n, либо даже если определил и он не ростёт, то изначальное кол-во ты не определил.

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

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

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

А чё ты так долго вымя мял, а просто не написал мне «ты прав»? Я ведь именно об этом и написал в своём первоначальном посте - что в памяти лежит некий индекс, из которого ему ясно, куда ходить на диске.

Производительность определяется не только сиками, но и трупутом. Ты, пока только в своих фантазиях, определил, что кол-во сиков от n не зависит. Но ты не определил зависимость роста трупута от n, либо даже если определил и он не ростёт, то изначальное кол-во ты не определил.

На трупут насрать, речь ведь идёт о рандомном доступе к одному ключу «wow=kiskismurmur».

Да и вообще. Своим «обычно» можешь подтереться. В цитате я этого не вижу. Либо пруфцуй, либо не болтай.

Ну чувак, если ты требуешь пруфы на такие стандартные для отрасли понятия, то куле меня обвиняешь в дебилизме. Big O notation в дисковых БД относится исключительно к числу дисковых операций. Что там лежит в памяти - накакано всем.

О боже. Не пиши мне ничего. Ты недостоин того, что-бы я тебе что-то писал. Ты даже не понял о чём я писал - ты настолько некомпетентен.

Иди подойди к пацанам с софии и скажи «хеши не нужны».

А чё ты так долго вымя мял, а просто не написал мне «ты прав»? Я ведь именно об этом и написал в своём первоначальном посте - что в памяти лежит некий индекс, из которого ему ясно, куда ходить на диске.

Ну и что за шизофрению ты мне написал? Какой ещё индекс и какой ещё памяти. Читай ответ в предыдущих комментариях.

Любое key-value это отображение хешей в индексы. В реальности массив с индексом хеш и значением индекс записи, либо индекс самого значения. O(хоть сколько) не имеет никакого отношение к тому где, что и как оно хранит.

Для обеспечения O(1) нам надо просто иметь динамический массивчик. При этом из этого не следует никак то, что за массивчиком у нас ничего нет. Там может быть хоть поиск перебором по 1кк елементам. Главное отвязать это от n. Это делается просто - я уже показал как. К n мы привязывает длину массива.

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

Сформулировано как на бухую голову.

1) Не любое k=v есть отображение хешей в индексы. У тебя может быть k=v в виде простого b-tree где нет никаких хешей, а отсортированные ключи в полном виде лежат в блоках. У тебя может быть в памяти AVL-дерево, где ключи тоже лежат в чистом виде. Неясно откуда у тебя взялись именно хеши так безоговорочно, что прям «любое k=v».

2) Динамический массивчик может лежать на диске? Что значит «за массивчиком ничего нет». «Быть за массивчиком» - это что конкретно означает? «Быть за» - это ёкарный насос что такое?

3) Как это делается - ты не показал. Ну или самому себе показал в уме, но забыл в пост добавить. Что значит «К n мы привязываем длину массива»? Это как? Где привязываем? Что за привязывание?

4) Когда пишут big O notation, тогда не разводят, я хотят сообщить что-то о производительности. Сам осознай это.

Ну и что за шизофрению ты мне написал? Какой ещё индекс и какой ещё памяти. Читай ответ в предыдущих комментариях.

Индекс - это некая структура данных, позволяющая по ключу найти индекс блока и его смещение в большом файле, например. Память - это ОЗУ, микросхемы DDR4 например, чёрненькие такие, ёкарны насос! В предыдущих комментах один бред нафигарен у тебя.

На трупут насрать, речь ведь идёт о рандомном доступе к одному ключу «wow=kiskismurmur».

Какая-такая речь? Речь идёт о производительности и несостоятельности привязки O(1) к производительности, которая её никак не определяет.

О боже. Не пиши мне ничего. Ты недостоин того, что-бы я тебе что-то писал. Ты даже не понял о чём я писал - ты настолько некомпетентен.

Иди подойди к пацанам с софии и скажи «хеши не нужны».

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

Какая-такая речь? Речь идёт о производительности и несостоятельности привязки O(1) к производительности, которая её никак не определяет.

При чём тут производительность? Ты глазами пробовал первоначальную фразу в топике читать?

It has guaranteed O(1) worst case complexity for read, write and range scan operations

Не вижу тут слова performance.

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

Читаем:

It is designed to provide best possible on-disk performance without degradation in time.

Тут написано, что он задизайнен для перфоманса с отсутствующей деградацией.

А далее уже следует попытка написать то же самое формальным языком:

It has guaranteed O(1) worst case complexity for read, write and range scan operations.

Т.е. это пруф этого утверждения:

without degradation in time

Но пруфа этого:

to provide best possible on-disk performance

Нету.

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

to provide best possible on-disk performance

Индекс - это некая структура данных, позволяющая по ключу найти индекс блока и его смещение в большом файле, например. Память - это ОЗУ, микросхемы DDR4 например, чёрненькие такие, ёкарны насос! В предыдущих комментах один бред нафигарен у тебя.

Ну что я могу сказать - в школу.

Сформулировано как на бухую голову.

Доказательства в студию.

Не любое k=v есть отображение хешей в индексы.

O(1) любое.

Динамический массивчик может лежать на диске? Что значит «за массивчиком ничего нет». «Быть за массивчиком» - это что конкретно означает? «Быть за» - это ёкарный насос что такое?

Причём тут диск?

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

Как это делается - ты не показал. Ну или самому себе показал в уме, но забыл в пост добавить. Что значит «К n мы привязываем длину массива»? Это как? Где привязываем? Что за привязывание?

Я показал. Если ты неспособен понять - разжевывать для тебя я не буду. Показал это вот тут:

нам надо просто иметь динамический массивчик.

Так уж и быть я тебе объясню. У нас есть 10 коробочек, в которых по 100шариков в каждой. В сумме у нас 1к шариков. Мы добавили ещё 1к. Сколько шариков будет в коробочке? 200.

Можем ли мы отвязать кол-во шариков в коробке от кол-ва шариков? Можем. Привязать его к кол-ву коробок.

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

Когда пишут big O notation, тогда не разводят, я хотят сообщить что-то о производительности. Сам осознай это.

Ну тут ты сам себя загнал в лужу. Поздрваляю.

Люблю спорить к экспертами. Достаточно чуть подождать и он сам себя загонит в лужу:

При чём тут производительность? Ты глазами пробовал первоначальную фразу в топике читать?

И

Когда пишут big O notation, тогда не разводят, я хотят сообщить что-то о производительности. Сам осознай это.

Вот так мы и выходим на то, что кто-то болтун.

При чём тут что я случайно сболтнул, если речь идёт только о фразе из первоначального поста? Ну ошибся я, ты ещё год будешь на этом сосредотачиваться?

Я объяснил причём тут фраза. И ты не ошибся. Мне было понятно, что это так и есть. Но далее тебе надо было как-то оправдываться.

Я тебе могу и другое вспомнить:

Тебя попросили пруфцануть про сики. Ты что мне ответил?

Ну чувак, если ты требуешь пруфы на такие стандартные для отрасли понятия, то куле меня обвиняешь в дебилизме. Big O notation в дисковых БД относится исключительно к числу дисковых операций. Что там лежит в памяти - накакано всем.

Т.е. ты тут определил то, что не понимаешь базовых, фундаментальных понятий. Хотя это ты это показал ещё тогда, когда начал говорить про сики. Почему? Потому что О(1) в базовом определение определяет рост времени, а значит и рост операций, ибо операции стоят время, а если не стоят, то их нет смысла считать. Значит туда входит всё и сики и не сики. И для этого не нужно какое-то отдельное определение сложности.

Мне было понятно, что это так и есть. Но далее тебе надо было как-то оправдываться.

Тут ошибка. Не мне, а тебе.

Чувак, ты реально трешово излагаешь мысль.

Чё-то ты углубился в разгребание эпистолярных противоречий. Сосредоточься на формулировке изначальных мыслей.

Как именно обеспечен поиск ключа за O(1)? Весь индекс ключей (например хеш-таблица) лежит всегда в ОЗУ, которая всегда даёт отсутствующий в памяти ключ за 1 seek?

Не сики туда не в ходят.

Потому что О(1) в базовом определение определяет рост времени

вы стоите друг друга. продолжайте

O(1) - это не «рост», а функция от числа данных. В данном случае функция всегда равна 1. У тебя хорошо сэмулирована «умность», «вьедливость» и «занудность», то свою тупость ты скрыть не сумел.

В данном случае функция всегда равна 1

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

вы стоите друг друга. продолжайте

Аргументацию завезите, пожалуйста.

завёз же. в тему комментария

Аргументацию завезите, пожалуйста.

Да насрать на него, давай продолжать )

O(1) - это не «рост», а функция от числа данных.

А где эти сами данные в ней? Поподробнее. Вот эта единичка?

В данном случае функция всегда равна 1.

Т.е. данных всегда 1? И «равна 1» - это в чём измеряется? В сиках. Т.е. на 1днных у нас 1сик? А почему данных 1? Как нам получить 2сика? Как получить 2данных?

У тебя хорошо сэмулирована «умность», «вьедливость» и «занудность», то свою тупость ты скрыть не сумел.

Действительно, поэтому ты в очередной раз перданул в лужу.

Нет. Ты спастил кусок из моего комментария. И намекнул на то, что я неправ. Именно аргументации за мою неправоту я и прошу, если моё определение в чём-то не соответствует действительности - поясни.

Что мне в тобою продолжать. Спорить с тобою смысла нет - ты нулёвый. Объяснять тебе что-то то же, ибо ты слишком ахреневший.

А самих данных в ней и нет, в том и прикол. Функция описывает зависимость от объёма данных так, что в этой зависимости не участвует объем данных, т.е. нет зависимости от объема данных. Иными словами, нам насрать сколько данных будет лежать, операции get, set, delete для некого ключа оно всегда выполнит за одно и то же время.

Что мне в тобою продолжать. Спорить с тобою смысла нет - ты нулёвый. Объяснять тебе что-то то же, ибо ты слишком ахреневший.

Да норм всё, ты-то тоже охреневший, чё в этом плохого? Это нормально! Я не нулёвый, просто ты через джоппу объясняешь как тормоз.

А самих данных в ней и нет, в том и прикол.

Ты мне не юли. Возвращает твоё функция что.

Да норм всё, ты-то тоже охреневший,

Нет.

чё в этом плохого?

В этом нет ничего плохого. Плоха именно пара, а именно ахреневший ноль, да к тому же ещё и болтун.

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

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

это не кусок из комментария, а феерический бред.

И как всегда доказательств нет. Только пердёжь в лужу.

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

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

Меня не интересует какие там множества - тебе нужно ответить функции эти чего и от чего. Что есть x и что он возвращает.

Тем более какого хрена ты припихнул сюда f(x)?

при этом выдавая какую-то шизофазию за определение.

Пока что это не более чем твой трёп. А твои попытки уровня «небо синее, поэтому трактор зелёный» ничего не стоят пока ты не свяжешь свои выводы с твоим же утверждение, а далее уже с моим. Т.е. каким образом из того, что трактор зелёный следует то, что у меня тут шизофрения.

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

потому что

«Потому что О(1) в базовом определение определяет рост времени»

«в базовом определение»

...

Тем более какого хрена ты припихнул сюда f(x)?

определение же

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

Я не понял, как оно обеспечит O(1)? Оно всегда хранит в памяти инфу, позволяющую получить конкретное смещение страницы в неком файле?

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

Очередной эксперт пытается играть со мною в игрульки. Зачем? Ведь я несоизмеримо сильнее.

потому что

Это всё хорошо, только вот я писал про интерпретацию полученных значений, а ты пытаешься съехать на какие-то инсинуации вокруг самих функций.

определение же

Определение чего?

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

Написать O(1) про дисковую БД - это сообщить вполне конкретную вещь, что у нас будет в худшем случае только 1 доступ к диску, 1 seek в худшем случае

Какая глупость. O(1) значит лишь то что число seek'ов не превысит некоторого фиксированного порога - может 1, а может и миллион, независимо от количества ключей хранящихся в БД.

Определение чего?

ты даже свои цитаты осмыслить не можешь? тогда у меня для тебя плохие новости...