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

Question

Учитывая 1 ГБ (очень большой) файл, содержащий слова (некоторые повторяются), нам нужно прочитать файл и вывести, сколько раз каждое слово повторяется.Пожалуйста, дайте мне знать, если мое решение обладает высокой производительностью или нет.

(Для простоты давайте предположим, что мы уже захватили слова в arraylist<string>)

Я думаю, что большой O (n)это "п".Я прав?

public static void main(String[] args) {

            ArrayList al = new ArrayList();
            al.add("math1");
            al.add("raj1");
            al.add("raj2");
            al.add("math");
            al.add("rj2");

            al.add("math");
            al.add("rj3");
            al.add("math2");
            al.add("rj1");
            al.add("is");
            Map<String,Integer> map= new HashMap<String,Integer>();

            for (int i=0;i<al.size();i++)
            {
                String s= (String)al.get(i);

                    map.put(s,null);

            }
            for (int i=0;i<al.size();i++)
            {
                String s= (String)al.get(i);
                if(map.get(s)==null)
                    map.put(s,1);
                else
                {
                    int count =(int)map.get(s);
                        count=count+1;
                        map.put(s,count);
                }


            }

            System.out.println("");
        }

Answer 1

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

Пища для размышлений по решению hashmap

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

Английский дик. Включенный в Linux имеет 400 тыс. слов и составляет около 5 МБ. Итак, из «1 ГБ» текста, который вы прочитали, мы можем предположить, что вы будете хранить только около 5 МБ в вашем HashMap. Оставшаяся часть файла будет преобразована в строки, которые нужно будет собрать в мусор после того, как вы поищете их на своей карте. Я могу ошибаться, но я полагаю, что байты будут повторяться снова во время создания String, поскольку массив байтов необходимо копировать внутренне и снова для вычисления 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.

Answer 2

Рассматривали ли вы использовать решение Mapreduce?Если набор данных становится больше, тогда было бы лучше разделить его на части и считать слова параллельно

Answer 3

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

Answer 4

Чтобы ответить на ваш вопрос, сначала вам нужно понять, как работает 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.

Answer 5

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

Нет необходимости ставить нули заранее - вы можете сделать это в основном цикле.) в обоих случаях, но вы хотите сделать константу как можно меньше.(O (n) = 1000 * O (n), справа :))