Ответ 1

проверить эту страницу https://developer.mozilla.org/en-US/docs/Web/JavaScript/Typed_arrays?redirectlocale=en-US&redirectslug=JavaScript%2FTyped_arrays, я содержит контейнеры javascript низкого уровня, я думаю, что один из них будет соответствовать вашим потребностям

Ответ 2

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

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

Ответ 3

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

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

Ответ 4

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

Затем я предлагаю оценить следующие параметры:

• попытайтесь использовать простые объекты как хэши вместо массивов
• перепишите свой код в Dart или Java и скомпилируйте его в JS, используя компилятор GWT и оценивать результаты
• попробуйте использовать шейдеры WebGL
• реализуйте части своего кода, используя собственный клиентский SDK или NPAPI (но следует предупреждать, что NPAPI устарел)

Ответ 5

Вот мой вариант:

• Если вы контролируете свой набор данных, вы можете попробовать использовать JS-числовое число (длиной 8 байт) для хранения большего количества значений (может быть, 4 значения, каждые 2 байта) - точное увеличение памяти зависит на фактическом диапазоне; также побитовые операции имеют тенденцию быть довольно быстрыми, поэтому не должно быть производительности

• Также вы можете попробовать обернуть ваши значения в объекте (например, OpNumeric), который является неизменным. Каждый раз, когда вам нужно числовое значение, вы запрашиваете NumericManager для завернутого экземпляра и сохраняете ссылку на OpNumeric. Таким образом, все значения 5 будут хранить ссылки на один и тот же объект OpNumeric (5); Я не уверен, какой размер ссылки в JS (это, вероятно, зависит от возможностей реализации и машины), но стоит попробовать. Также OpNumeric является хорошим кандидатом для реализации (1). Это немного снизит производительность и, вероятно, временно увеличит использование памяти, но это должно быть только при разрешении ссылок OpNumeric.

• Если вы создаете свои массивы "на лету" (а не добавляя значения один за другим), возможно, стоит хэшировать и повторно использовать их. Поскольку вы уже знаете диапазон, вы можете придумать хэш, который даст вам как можно меньше коллизий; и даже если у вас есть пара-столкновений, то должно быть достаточно хорошо разбираться в ЦП, чтобы выбрать правильную ссылку по значению путем сравнения значений.

Извините, это не прямой ответ, но с такими вещами нет прямого способа достижения цели. Возможно, стоит посмотреть asm.js. Кажется, что у вас есть что-то общее с тем, что вы делаете.

Приветствия,

Ответ 6

Я смею рассказывать мифологическую мысль.

В этой мифологической мысли

• У вас будет статический массив из 0-65k ints - отсортировано.
• Массив, содержащий metadata для каждого из ваших объектов A и...
  • slice(x,y) получит кусок массива, начинающийся с x и заканчивающийся на y из статического массива шага 1.
  • dupeof(oldarray) вернет oldarray во время выполнения.
  • diff, который вычисляет разницу двух массивов
  • sort, который будет сортировать массив ints... [].sort(function(a,b){ return a-b; });
• Массив dupes для хранения уникальных повторяющихся массивов.

В дополнение к этой мифологии, это то, что я желаю, чтобы мы могли сделать...

• Когда вы создаете новый объект (ваш A), вы будете sort его массив, slice из статического массива от первого значения этого A до последнего значения этого A, найдите diff из slice d one и вашего текущего массива A, который меньше, чем когда-либо.

• Учитывая этот сценарий, примерная запись (metadata для объекта A) будет выглядеть так: "0-11,[3,5]". В более простом английском языке его следует понимать как construct an array from static array, slice from 0 to 11, and remove 3, 5 from that slice. Мы получили бы [0,1,2,4,6,7,8,9,10,11,12].

• Вы должны сделать свой конструктор A через эту логику, когда она будет построена. Итак, в любой момент времени у вас будет только metadata ваших объектов (Your A: s). И ваш код будет читать эти данные, чтобы построить вашу сетку "на лету" во время выполнения.

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

Ответ 7

Я работал над системами, которые отображали на веб-странице таблицы с разбивкой по страницам, содержащие до двадцати пяти тысяч строк данных клиента, включая 10 столбцов имени, возраста, адреса, телефона и т.д., и, как вы можете себе представить, мы искали способы оптимизации отображения этих данных.

Очевидно, что построение одной большой поисковой, сортируемой таблицы на веб-странице и попытки сохранить все эти данные было болотом памяти (вы можете представить, что он сделал с IE7/8).

Четыре решения, с которыми я столкнулся:

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

• Если локальное хранилище недоступно, я бы загрузил объект Flash в и он извлекал данные с сервера, и я использовал ExternalInterface для доступа к данным по мере необходимости.

• Если Flash не был доступен, я бы сохранил его в Java-апплете и доступ он аналогичным образом.

• Отсутствие каких-либо из этих параметров, пользователь должен был немного пострадать. Им нужно будет ввести некоторые параметры поиска, и они только данные, возвращаемые через вызов ajax и только в управляемых ломти. Но если у них не было локального хранилища, Flash или Java они получили то, что они заслужили.;)

Ответ 8

В зависимости от того, насколько разрежен ваш массив, вы можете захотеть сохранить диапазоны целых чисел, где обычно у вас будут непрерывные последовательности целых чисел в вашем массиве (т.е. [[1, 5], [10, 14]] вместо [1, 2, 3, 4, 5, 10, 11, 12, 13, 14] или даже [1, 5, 10, 14], так как ваш код может считать, что он отформатирован парами). Если ваш массив очень разрежен, вы все равно можете использовать этот метод, сохраняя диапазоны пробелов в последовательности. Чтобы дать вам идею:

function IntegerArray(integers) {
  this.ranges = [];
  // Convert integers to ranges (Don't have time to overview algorithm,
  // but I think a good start would be sorting the integers and searching
  // for gaps)
}
IntegerArray.prototype = {
  insert: function (n) {
    // Could achieve O(log n) time complexity with binary search since
    // the ranges are sorted.
    // * n is between two ranges = insert [n, n] range.
    // * n is 1 less than the start of a range = decrease range start by 1.
    // * n is 1 more than the end of a range = increase range end by 1.
  },
  remove: function (n) {
    // Also O(log n) time complexity with binary search.
    // * n has [n, n] range = remove range.
    // * n is at beginning of range = shift range.
    // * n is at end of range = pop range.
    // * n is in middle of range = split range.
  }
};

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

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

• Начальная точка: наименьшее целое число в вашем массиве.
• Массив целых чисел, представляющий размер целых диапазонов (как положительные целые числа) и пробелы (как отрицательные целые числа) вместо самих индексов.

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

Ответ 9

Идея использования специальной структуры (string или big int с битовой маской) для воссоздания массива каждый раз, я думаю, неверна. Это заставит вас повторно создавать массивы снова и снова, и накладные расходы, которые вы будете вводить при этом (дополнительное время процессора + время GC), вероятно, не стоит этого. Как и в базе данных, вычисленное поле является справедливой игрой для крошечных объемов данных, но взорвется в вашем лице, когда у вас большие суммы, - лучше хранить рассчитанный и непосредственно используемый результат, если показатели производительности.

Идея использования хэш-таблицы имеет, я думаю, немного больше достоинства. Но здесь есть компромисс, поскольку это зависит от того, как ваши сферы вращаются. Вы говорите в своем вопросе:

Каждая ячейка содержит список идентификаторов (положительных целых чисел), которые указывают на объекты сферы, которые ячейка пересекает.

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

Imo, рассмотрите возможность перечисления объектов непосредственно, вместо использования и сохранения их идентификаторов. В любом случае каждый объект будет существовать, и я предполагаю, что каждый из них должен поддерживать массив пересекающихся сфер по соображениям производительности в любом случае. Таким образом, также не может добавлять накладные расходы (время памяти + время доступа) дополнительных ID.

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

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

Ответ 10

массив положительных целых чисел, таких как [0, 1, 4], [1, 5, 74, 1013] и т.д. Им не нужно иметь личное значение, все объекты могут использовать один и тот же список. Количество томов может идти от 0 до нескольких тысяч, скажем, 65 тыс. (Короткое).

Один из способов

Замена массива int с массивом флагов в массив int имеет смысл, если массивы имеют большие объекты. Но поскольку они являются короткими целыми числами, преимущество, вероятно, минимальное.

Возможна возможность замены чисел массивами 32-битовых флагов чисел, то есть, например,

[ 10, 13, 1029 ]

может быть переведена в блоки размером 32, в которых 10 и 13 будут попадать в один и тот же блок, и может быть кодировано (1 < 10) | (1 < < 13). Но для этого вам нужно, чтобы каждый список содержал все счетчики, что означает 2048 32-битных целых чисел, большинство из которых были бы равны нулю.

Вариант (тип кодировки с длиной строки), если у вас есть большинство чисел, очень близких друг к другу - в пределах 32 целых чисел друг от друга) может состоять в том, чтобы хранить каждый "запуск" чисел в виде пары, один описывая первое число N, а другое кодирует следующие числа, вплоть до N + 32. Итак:

 15, 21, 27, 29, 32, 40, 44

становится:

 15, (21-16=)5, (27-16=)11, 13, 16, 24, 28

а затем:

 15, 1<<5 + 1<<11 + 1<<13 + 1<<16 + 1<<24 + 1<<28

чтобы вы могли сохранить 6 дополнительных сокращений в одном 32-битном значении. Это работает, только если массивы "сбиты". Если у вас больше всего разбросанных чисел, дальше от 32, это определенно не будет стоить усилий.

Кроме того, вы должны учитывать стоимость обращения с такими числами, т.е. стоимость переинсталляции сжатого массива, чтобы что-то с ним делать.

Другой способ

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

[ [ 0, 1, 4 ],             // ID#0
  [ 1, 5, 74, 1013 ],      // ID#1
]

что означает, что поиск того, существует ли массив или нет, будет стоить. Вам также нужно будет добавить индекс:

{ "1": { "5": { "74": { "1013": { "-1": 1 // The array ending here has id 1

Теперь вы сохраняете [1, 5, 74, 1013, 1089], когда вы приходите к ключу 1013, вы не находите ключ 1089, поэтому вы знаете, что это не дубликат, сохраните его в основном массиве, восстановите его index - say 1234 - и добавить "1089": { "-1": 1234} к ключу 1013.

Добавление массива достаточно быстро, так как оно обращается к его значениям.

Память, стоит ли это? Каждый массив вместо N целых чисел теперь состоит из N целых чисел плюс (N + 1) словарей с по меньшей мере одним целым числом, поэтому я бы сказал, что стоимость находится между утроенными и четырехкратно. Если дубликатов массивов очень много, это может быть выгодным; иначе это может быть не так. Если меньше, скажем, одна треть массивов - это дубликаты, вероятно, этого не будет.

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

 [ 1 ]       [ 1 ]      [ 1 ]
 [ 2 ]       [ 2 ]      [ 2 ]
 [ 3 ]  -->        -->  [ 5 ]
 [ 4 ]       [ 4 ]      [ 4 ]
 [ 5 ]       [ 5 ]      

Twist

Вместо массива и дерева выше, вы можете хэш-список и использовать хеш в качестве идентификатора. Однако это может привести к конфликтам, если вы не использовали строковый список (стрицированный вами или JS - первый метод thriftier, второй быстрее) в качестве ключа. В этом случае вам потребуется в среднем, скажем, четыре байта на каждое целое число в ключе; меньшие числа будут весить меньше, хотя, поскольку "1.12.13.15.29" составляет всего около 14 байт или около того. Объем памяти будет приблизительно утроен для уникальных массивов и обнулен для дубликатов; опять же все приходит к тому, сколько дубликатов там по сравнению с не дублированными.

Ответ 11

Нечто похожее делается для lucene/solr. Не стесняйтесь проверять https://github.com/apache/lucene-solr/blob/trunk/solr/core/src/java/org/apache/solr/search/DocSetCollector.java Это java, но я уверен, вы можете использовать ту же идею для javascript.

Короче говоря, сначала они хранят массив int

// in case there aren't that many hits, we may not want a very sparse
// bit array.  Optimistically collect the first few docs in an array
// in case there are only a few.
final int[] scratch;

Но позже, если количество совпадающих документов слишком много, они переключаются на BitSet, который просто

bits = new OpenBitSet(maxDoc);

Здесь maxDoc - максимальное количество элементов в списке. Я не знаю, можете ли вы найти номер в своей задаче, но, может быть, вы знаете, что в списке не больше N целых чисел. (похоже, вы упомянули 65k).

Итак, если у вас есть числа, скажите 1,2,3,4,5,6,7,8,9,10, тогда, когда у вас есть целые числа, у вас есть 10 * 32 бита, который составляет 320 бит. Но если вы выделяете биты с размером 10, то это всего лишь 10 бит. Если 1-й бит является истинным, тогда у вас есть 1 в вашем списке, если 10-й бит истинен, тогда у вас есть 10 в вашем списке. Таким образом, ваш порог для переключения составляет 2048 элементов. 2048 целых чисел - 65536 бит, но с битрейтом вы можете кодировать 65536 элементов вместо 2048.

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

Ответ 12

• найти более эффективный для хранения памяти способ хранения списков тиков

Обратите внимание, что JavaScript не имеет целых чисел, только числа с плавающей запятой.

(Может быть, массив бит в больших числах?)

Я уверен, что у JavaScript нет битовых операторов. (Побитовые операции с плавающей запятой не имеют смысла)

Найдите способ избежать дублирования.

Это позволило бы избежать большой памяти, если бы вы могли: 1) обнаружить дубликаты, 2) указать их на один и тот же базовый объект. Это должно быть довольно тривиально, если вы строите структуру раньше времени. Но обнаружение дубликатов во время выполнения снижает производительность. Вам нужно будет проверить, сколько. В верхней части моей головы я бы сказал, что нужно хранить массивы в Trie. Ваши объекты будут иметь прямой указатель на массив, но при добавлении нового массива вы проходите через Trie. Это предотвращает дублирование.

Есть ли у вас предложение?

Если вы работаете в браузере, загляните в проект под названием asm.js. Это позволит вам использовать ints.

Ответ 13

Хранить каждый массив в виде строки. Строка по существу представляет собой набор шорт (UTF16) и interning время выполнения позволит избежать дополнительного хранения для идентичных массивов/строк. Используйте String.fromCharCode(), чтобы преобразовать числовое значение UTF16 в односимвольную строку. Используйте String.charCodeAt() для извлечения чисел из строки.

Так как JavaScript невнимателен в отношении таких символов, как специальные символы Юникода, такие как объединение символов акцента и даже недопустимых символов, length будет работать так, как вы ожидаете. То есть, это даст вам число "charCodes", а не количество символов Unicode.

Ответ 14

Вы можете использовать битсет. Существуют эффективные библиотеки, реализующие биты в JavaScript. См. Например:

https://github.com/lemire/FastBitSet.js