Это достаточно сложная идея, чтобы обернуть мою голову, и я был бы очень признателен за любые изменения / помощь, чтобы сделать его более читаемым для тех, кто в курсе.
Возможно ли теоретически иметь жесткий диск, на котором сохранена одна копия каждой возможной двоичной перестановки в один килобайт, а затем остальная часть системы просто создаст указатели на эти места?
Будет ли система, созданная таким образом, быстрее, чем просто хранить информацию напрямую?
Чтобы объяснить по-другому, скажите вместо предложения:
"Привет, я Боб." и "Этот бутерброд выглядит вкусно".
... сохраненные на жестком диске, мы имели бы все перестановки алфавита и других символов вплоть до некоторого числа (скажем, 1000 символов или около того), а затем сохраняли бы наши предложения как что-то вроде:
[Указатель # 21381723]
источник
Ответы:
Есть 2 8192 возможных различных блоков 1К. Хранение их всех займет 2 8202 бита. Поскольку Вселенная содержит только около 10 80 (или ~ 2 266 ) частиц, это безопасная ставка , что это не возможно , чтобы сохранить их все, и вы не должны задаться вопросом о том, будет ли сэкономить время или нет.
Но на самом деле есть более интересный способ ответить на этот вопрос. Вы предлагаете создать индекс в виде огромного пула констант. Но как бы вы узнали, какой индекс для разыменования? Представьте себе , ради аргумента , что вы хотите сохранить только 1-символы блоки:
a,b,c... Предположительно ваши индексы будут 0, 1, 2 и т.д., так как это наиболее эффективное расположение хранения этих блоков.Вы заметили что-то о договоренности? Фактически, ваш индекс является кодированным представлением хранимых данных ! Другими словами, вам вообще не нужно разыменовывать, вам просто нужно преобразовать индекс в нужные вам данные.
Когда вы сохраняете все возможные значения чего-либо в таблице, это всегда происходит: ваш индекс становится просто зашифрованной версией самих данных, поэтому сохранение данных становится ненужным в первую очередь. Это почему в реальном мире, показатели полезны только для разреженных данных (например , всех веб - страниц , которые вы посетили, не все веб - страницы , которые могут существовать , или даже все , что делают существуют).
источник
Как уже отмечали другие, у вас есть 2 ^ 8192 возможностей для блока 1k. Это означает, что вам потребуется 8192 бита для кодирования адреса блока, если адреса всех блоков кодируются одинаковым количеством битов, поэтому ваши адреса будут иметь длину 1 КБ. Вы не получили бы ничего, кроме добавления слоя косвенности, чтобы не получить никакой производительности.
Если вы хотите иметь более короткие адреса, вам придется кодировать некоторые блоки с коротким адресом, а некоторые - с более длинными, и делать так, чтобы длинные не появлялись так часто, и теперь вы просто сжимаете данные (возможно, что-то вроде код Хаффман ). Это потребует знания данных, которые вы сохраняете, перед их сохранением или регулярных изменений в кодировке. Это также, вероятно, будет менее эффективным, чем другие алгоритмы сжатия, которые используют блоки различной длины.
источник
Есть две проблемы с этим.
Во-первых, «все возможные двоичные перестановки в один килобайт» - это огромное количество данных. 1024 байта * 8 бит на байт = 8192 бит на килобайт. Все возможные перестановки будут 2 ^ 8192. Это около
1.09e+2466килобайта! (Для сравнения: 1 ТБ диска - это1e09килобайт.)Во-вторых, даже если бы у вас была такая огромная таблица, и вы проиндексировали ее с помощью указателей, что бы вы сделали, если бы захотели ссылаться на некоторые данные размером менее 1 КБ?
источник
Как отмечали другие авторы, в какой-то момент размер указателя, необходимый для индексации в вашем списке всех возможных значений, сводит на нет ваш выигрыш.
Однако некоторые языки используют ограниченную версию того, что вы предлагаете, чтобы оптимизировать использование памяти. Python использует строку 'interning', чтобы уменьшить количество повторяющихся строк в памяти. Вы можете найти более подробную информацию, выполнив поиск по строке «python string intern».
источник