Выявление повторяющихся элементов в списке, содержащем 300 тыс. Строк +

Question

У меня есть список, содержащий 305899 строк (это имя пользователя для веб-сайта). После удаления всех дубликатов число уменьшается до 172123 строк.

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

private static Map<String, Integer> findNumberOfPosts(List<String> userNameList) {
    Map<String, Integer> numberOfPosts = new HashMap<String, Integer>();
    int duplicate = 0;
    int size = userNameList.size();
    for (int i = 0; i < size - 1; i++) {
        duplicate = 0;
        for (int j = i + 1; j < size; j++) {
            if (userNameList.get(i).equals(userNameList.get(j))) {
                duplicate++;
                userNameList.remove(j);
                j--;
                size--;

            }
        }
        numberOfPosts.put(userNameList.get(i), duplicate);
    }

    return numberOfPosts;
}

Затем я изменил это на:

private static Map<String, Integer> findNumberOfPosts(List<String> userNameList) {
    Map<String, Integer> numberOfPosts = new HashMap<String, Integer>();

    Set<String> unique = new HashSet<String>(userNameList);

    for (String key : unique) {
        numberOfPosts.put(key, Collections.frequency(userNameList, key));
    }

    return numberOfPosts;
}

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

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

Answer 1

Ваш метод findNumberOfPosts находится на правильном пути, но ваша реализация выполняет множество ненужной работы.
Попробуйте это:

private static Map<String, Integer> findNumberOfPosts(List<String> userNameList) {
    Map<String, Integer> numberOfPosts = new HashMap<String, Integer>();

    for (String userName : userNameList) {
        Integer count = numberOfPosts.get(userName);
        numberOfPosts.put(userName, count == null ? 1 : ++count);
    }
    return numberOfPosts;
}

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

Answer 2

Посмотрите, работает ли этот вариант вашего второго метода быстрее:

private static Map<String, Integer> findNumberOfPosts(
        List<String> userNameList) {
    Map<String, Integer> numberOfPosts = new HashMap<String, Integer>();

    for (String name : userNameList) {
        Integer count = numberOfPosts.get(name);
        numberOfPosts.put(name, count == null ? 1 : (1 + count));
    }

    return numberOfPosts;
}

Он имеет некоторые накладные расходы на упаковку / распаковку, но должен работать намного быстрее, чем то, что вы делали, что требовало перебора всего списка имен для каждого уникального имени.

Answer 3

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

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

Answer 4

Это идет даже быстрее, чем богемный:

private static Map<String, Integer> findNumberOfPosts(List<String> userNameList) {

        Map<String, Integer> numberOfPosts = new HashMap<String, Integer>();

        for (String userName : userNameList) {
            if (!numberOfPosts.containsKey(userName)) {
                numberOfPosts.put(userName, Collections.frequency(userNameList, userName));
            }
        }

        return numberOfPosts;
    }

Answer 5

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

List<String> userNameList = new ArrayList<String>();
// add elements to userNameList, including duplicates

userNameList.add("a");
userNameList.add("a");
userNameList.add("a");
userNameList.add("a");

userNameList.add("b");
userNameList.add("b");
userNameList.add("b");
userNameList.add("b");

userNameList.add("c");
userNameList.add("c");
userNameList.add("c");
userNameList.add("c");

int originalSize=userNameList.size();

HashSet hs = new HashSet();   //Set would handle the duplicates automatically.
hs.addAll(userNameList);
userNameList.clear();
userNameList.addAll(hs);

Collections.sort(userNameList);  //Sort the List, if needed.

//Displays elements after removing duplicate entries.
for(Object element:userNameList)
{
    System.out.println(element);
}

int duplicate=originalSize-userNameList.size();

System.out.println("Duplicate entries in the List:->"+duplicate); //Number of duplicate entries.

 /*Map<String, Integer> numberOfPosts = new HashMap<String, Integer>();   //Store duplicate entries in your Map using some key.
 numberOfPosts.put(userNameList.get(i), duplicate);

 return(numberOfPosts);*/

Answer 6

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

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

Answer 7

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

Map<String, Integer> map;
for (String username : usernames) {
    if (!map.containsKey(username)) {
        map.put(username, new Integer(0));
    } else {
        map.put(username, new Integer(map.get(username).intValue() + 1));
    }
}
return map;

Answer 8

Лучшее решение - добавить все элементы в массив, а затем отсортировать этот массив.

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