Как считать повторяющиеся слова?

Теоретически, поскольку доступ к HashMap обычно равен O (1), я предполагаю, что ваш алгоритм равен O (n), но на самом деле он имеет несколько недостатков. В идеале вы должны перебирать содержимое файла только один раз, обрабатывая (т.е. подсчитывая) слова, пока вы их читаете. Нет необходимости хранить все содержимое файла в памяти (ваш ArrayList). Вы перебираете содержимое три раза: один раз, чтобы прочитать его, а второй и третий раз в двух циклах кода выше. В частности, первый цикл в приведенном выше коде совершенно не нужен. Наконец, использование HashMap будет медленнее, чем необходимо, потому что размер по умолчанию при построении очень мал, и ему придется несколько раз увеличиваться внутри, заставляя каждый раз перестраивать хеш-таблицу. Лучше начать с размера, соответствующего тому, что вы ожидаете от него. Вы также должны учитывать коэффициент нагрузки.

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

Пища для размышлений о решении для хэш-карт

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

Английский дик. входящий в состав Linux, содержит 400 тыс. слов и имеет размер около 5 МБ. Таким образом, мы можем предположить, что из «1 ГБ» текста, который вы прочитали, вы будете хранить только около 5 МБ в своей HashMap. Остальная часть файла будет преобразована в строки, которые нужно будет удалить после того, как вы закончите их поиск на карте. Я могу ошибаться, но я считаю, что байты будут повторяться снова во время построения строки, поскольку массив байтов необходимо копировать внутри и снова для вычисления HashCode. Таким образом, решение может тратить изрядное количество циклов ЦП и заставлять GC выполняться часто.

Вполне нормально указывать на такие вещи в интервью, даже если это единственное решение, которое вы можете придумать.

Я могу рассмотреть возможность использования собственной RadixTree или структуры, подобной Trie.

Помните, как работает метод вставки RadixT/Trie. Который должен взять поток символов/байтов (обычно строку) и сравнить каждый элемент с текущей позицией в дереве. Если префикс существует, он просто продвигается вниз по дереву и потоку байтов на шаге блокировки. Когда он достигает нового суффикса, он начинает добавлять узлы в дерево. Как только достигается конец потока, он помечает этот узел как EOW. Теперь представьте, что мы могли бы сделать то же самое при чтении гораздо большего потока, сбрасывая текущую позицию в корень дерева каждый раз, когда мы нажимаем пробел.

Если бы мы написали собственное дерево Radix (или, может быть, Trie), узлы которого имели бы счетчики конца слова (вместо маркеров) и метод вставки считывался непосредственно из файла. Мы могли бы вставлять узлы в дерево по одному байту/символу за раз, пока не прочитаем пробел. В этот момент метод вставки будет увеличивать счетчик конца слова (если это существующее слово) и сбрасывать текущую позицию в дереве обратно в начало и снова начинать вставлять байты/символы. Принцип работы поразрядного дерева заключается в сворачивании повторяющихся префиксов слов. Например:

The following file:

math1 raj1 raj2 math rj2 math rj3 

would be converted to:

(root)-math->1->(eow=1)
     |    |-(eow=2)
     |    
      raj->1->(eow=1)
      | |->2->(eow=1)
      | |->3->(eow=1)
      j2->(eow=1)

Время вставки в такое дерево будет равно O(k), где k — длина самого длинного слова. Но так как мы вставляем/сравниваем по мере чтения каждого байта. Мы не более неэффективны, чем просто чтение файла, как мы уже должны.

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

Вы рассматривали возможность использования решения mapreduce? Если набор данных становится больше, то действительно было бы лучше разделить его на части и считать слова параллельно.

Вы должны прочитать файл со словами только один раз.

Не нужно заранее ставить нули — это можно сделать в основном цикле.

Сложность действительно O(n) в обоих случаях, но вы хотите сделать константу как можно меньше. (О(n) = 1000 * O(n), верно :) )

Чтобы ответить на ваш вопрос, во-первых, вам нужно понять, как работает HashMap. Он состоит из сегментов, и каждый сегмент представляет собой связанный список. Если из-за хеширования другая пара должна занять то же самое ведро, она будет добавлена ​​в конец связанного списка. Таким образом, если карта имеет высокий коэффициент загрузки, поиск и вставка больше не будут O (1), и алгоритм станет неэффективным. Более того, если коэффициент загрузки карты превышает заданный коэффициент загрузки (по умолчанию 0,75), вся карта будет перехэширована.

Это выдержка из JavaDoc http://download.oracle.com/javase/6/docs/api/java/util/HashMap.html:

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

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

Map<String,Integer> map= new HashMap<String,Integer>(al.size());

Без этого ваше решение недостаточно эффективно, хотя и имеет линейную аппроксимацию O(3n), так как из-за амортизации перехеширования вставка элементов будет стоить 3n вместо n.