Допустим, у вас есть массив в JavaScript.
var a = []
Затем вы заполняете этот массив 10 миллионами значений (произвольные значения, например, строки, целые числа, логические значения, числа с плавающей точкой в одном массиве, даже элементы dom),
a == [ 1, true, false, 2.2, 'hello world', 3.3, 1, 'foo', ... ]
Затем вы удаляете кучу элементов из массива в кажущихся произвольными позициях.
a == [ 1, undefined, false, undefined, undefined, 3.3, 1, undefined, ... ]
Таким образом, теперь в массиве теперь есть, казалось бы, случайно расположенные пустые слоты.
Прежде чем я продолжу, вопрос состоит в том, как сжать / сгруппировать / сгруппировать оставшиеся элементы в (возможно, новый) массив так, чтобы они занимали минимальное пространство, и все же это не занимало много вычислительной мощности/ время, чтобы выяснить, как изменить расположение элементов в массиве. У нас может быть столько метаданных о массиве для хранения вещей, сколько мы хотели бы в разумных пределах, но только когда он перераспределяет массив, он делает этоэффективно.Я думаю, что запускать этот браузер со многими графическими приложениями, работающими одновременно, должно быть эффективно.
Чтобы углубиться, первая оптимизация, которую я сделал с этой системой, заключается в отслеживаниииз индексов элементов, которые были удалены из массива, и просто выполните a[i] = undefined, а не a.splice(i, 1).Это хорошо работает, если вы добавляете один элемент, затем удаляете один, затем добавляете n и удаляете n, потому что слоты undefined переполняются новыми элементами (если вы добавляете / удаляете быстро).
Но это ломается в случае, если у вас есть 10 миллионов предметов, а затем случайным образом удаляют миллион из них.Теперь у нас есть вторичный индекс, отслеживающий 1 миллион неиспользуемых индексов и 1 миллион undefined слотов, поэтому массив занимает память, которая ему не нужна (sidenote, если v8 оптимизирует это, тогда просто рассмотрите Uint8Array иликак вместо этого, в этом случае я почти уверен, что все эти неопределенные значения (или нули, если мы сделаем 0 неопределенным для Uint8Array) будут занимать место)1024 * наиболее оптимизированным способом из возможных (имея в виду, что у нас могут быть метаданные о массиве, чтобы помочь с процессом), чтобы реорганизовать его и сэкономить место, оставаясь быстрым алгоритмом и не используя много эфемерной памяти,Я не знаю, но это кажется сложной проблемой, и поэтому я не знаю, куда лучше идти.
Я не хочу просто воссоздавать массивы все время и повторять весь массиви пропустить любые неопределенные.Мне бы хотелось, чтобы что-то, возможно, каким-то образом брало элементы, разделенные пробелами, и помещало их в более аккуратные куски, а затем нажимало их в начале массива, только тогда, чтобы понять, что теперь у нас есть 10000 слотов в конце, которые мы можем удалить, и затем создает новый массив, который на 10000 короче.Этот тип вещи.Так что, возможно, эвристика, которая звучит хорошо, это просто воссоздать массив каждый раз, когда есть 10000 пустых слотов.Но я не уверен, что это так просто.