Как подсчитать строку num с лимитной памятью?

Ответ 1

Я сосать объяснение теоретических ответов, но здесь мы идем....

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

• Память, используемая для хранения всех отдельных слов, составляет 80 МБ (весь файл больше).
• Слова могут содержать символы не-ascii (поэтому мы просто обрабатываем данные как необработанные байты).

Достаточно прочитать файл, дважды записывая ~ 40 МБ разных слов.

//  Loop over the file and for each word:
//
//      Compute a hash of the word. 
//      Convert the hash to a number by some means (skip if possible).
//      If the number is odd then skip to the next word. 
//      Use conventional means to store the distinct word. 
//
//  Do something with all the distinct words. 

Затем повторите вышеуказанный второй раз, используя even вместо odd.

Затем вы разделили задачу на 2 и можете делать каждый отдельно. Во втором наборе никаких слов из первого набора не появится.

Хэш необходим, потому что слова могут (теоретически) заканчиваться одной буквой.

Решение может быть расширено для работы с различными ограничениями памяти. Вместо того, чтобы говорить просто нечетно/даже, мы можем разделить слова на X-группы, используя number MOD X.

Ответ 2

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

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

Я считаю, что это сообщение может вам помочь. Или выполните поиск самостоятельно внешняя сортировка.

Обновление 1

Или, как @jordeu, вы можете использовать встроенную библиотеку баз данных Java: например, H2, JavaDB или similars.

Обновление 2

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

Ответ 3

Прочитайте одну строку за раз и затем, например, a HashMap<String,Integer> где вы помещаете свои слова в качестве ключа, а count - как целое.

Если существует ключ, увеличьте количество. В противном случае добавьте ключ к карте со счетом 1.

Нет необходимости хранить весь файл в памяти.

Ответ 4

Я предполагаю, что вы имеете в виду количество разных слов?

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

Чтобы уменьшить потребности в памяти, вы можете рассчитать контрольную сумму для слов и сохранить это вместо самих слов. Хранение, например. 4-байтная контрольная сумма вместо 8-символьного слова (требующая хранения не менее 9 байтов) требует 40M вместо 90M. Плюс вам нужен счетчик для каждого слова. В зависимости от ожидаемого количества вхождений для определенного слова вы можете обойтись с помощью 2 байтов (для максимальных 65535 случаев), что требует максимальной памяти 60 МБ для 10M различных слов.

Update

Конечно, контрольная сумма может быть рассчитана по-разному, и она может быть без потерь или нет. Это также сильно зависит от набора символов, используемого в словах. Например. если используются только строчные стандартные символы ASCII (как показано в приведенных выше примерах), у нас есть 26 разных символов в каждой позиции. Следовательно, каждый символ может быть без потерь закодирован в 5 бит. Таким образом, 8 символов вписываются в 5 байтов, что немного превышает лимит, но может быть достаточно плотным, в зависимости от обстоятельств.

Ответ 5

Используйте H2 Database Engine, он может работать на диске или в памяти, если это необходимо. И у него действительно хорошая производительность.

Ответ 6

Я бы создал SHA-1 каждого слова, а затем сохранил эти числа в наборе. Затем, конечно, при чтении номера проверьте Set, если он там [(не совсем необходим, поскольку Set по определению является уникальным, поэтому вы можете просто "добавить" его номер SHA-1 также)]

Ответ 7

В зависимости от того, какой тип слова вы создадите для себя, вы можете выбрать для этой системы:

Если он может содержать любой символ алфавита в верхнем и нижнем регистре, у вас будут комбинации (26 * 2) ^ 8, что равно 281474976710656. Это число может вписываться в длинный тип данных.

Итак, вычислите контрольную сумму для таких строк:

public static long checksum(String str)
{
    String tokes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    long checksum = 0;

    for (int i = 0; i < str.length(); ++i)
    {
        int c = tokens.indexOf(str.charAt(i));

        checksum *= tokens.length();
        checksum += c;
    }

    return checksum;
}

Это уменьшит принятую память на слово более чем на 8 байтов. Строка представляет собой массив из char, каждый char находится в Java 2 байта. Итак, 8 символов = 16 байт. Но класс string содержит больше данных, чем только массив char, он содержит также целые числа для размера и смещения, что составляет 4 байта на int. Не забудьте также указатель на память для строк и массивов char. Итак, исходная оценка заставляет меня думать, что это уменьшит 28 байт на слово.

Итак, 8 байт на слово и у вас 10 000 000 слов, дает 76 МБ. Это ваша первая неправильная оценка, потому что вы забыли все, что я заметил. Таким образом, это означает, что даже этот метод не будет работать.

Ответ 8

Если вы можете сначала отсортировать файл (например, используя утилиту "сортировать" по умолчанию в Unix), тогда это легко. Вы просто читаете отсортированные элементы, считая соседние дубликаты, когда идете, и сразу же записываете итоговые данные в новый файл.

Если вам нужно сортировать с помощью Java, этот пост может помочь:

http://www.codeodor.com/index.cfm/2007/5/10/Sorting-really-BIG-files/1194

Ответ 9

Вы можете преобразовать каждое 8-байтовое слово в long и использовать TLongIntHashMap, который довольно эффективен, чем Map<String, Integer> или Map<Long, Integer>

Если вам просто нужны разные слова, вы можете использовать TLongHashSet

Ответ 10

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

Основная идея:

Рассматривайте файл как n разделов p_1... p_n, размер которого можно загрузить каждый из них в RAM.

• Загрузите p_i в структуру карты, просмотрите весь файл и отслеживайте только количество элементов p_i (см. ответ Heiko Rupp)
• Удалить элемент, если мы встретим одно и то же значение в разделе p_j с j меньше i
• Результат результата рассчитывается для элементов на карте
• Очистить карту, повторить для всех p_1... p_n

Ответ 11

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

Ваш скудный ресурс - это память, поэтому вы не можете хранить слова в ОЗУ.

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

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

Итак, мое предложение состоит в том, чтобы перебирать файл и для каждого слова:

• Если слово было найдено в первый раз, напишите строку в файл результата вместе с целым значением 1.
• Если слово было обработано ранее (оно появится в файле результатов), увеличьте значение записи.

Это решение хорошо масштабируется независимо от количества строк вашего входного файла или длины слов *.

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

EDIT:
* Он хорошо масштабируется, пока не закончится дисковое пространство XD. Таким образом, предварительным условием было бы иметь диск с не менее чем 2N байтами свободного полезного пространства, где N - размер входного файла в байтах.

Ответ 12

возможные решения:

• Используйте сортировку файлов, а затем просто подсчитайте последующие вхождения каждого значения.
• Загрузите файл в базу данных и используйте оператор count следующим образом: select value, count(*) from table group by value