ява - Удалить почти дубликаты из списка

Question

У меня есть список объектов Tweet (доморощенный класс), и я хочу, чтобы удалить ОКОЛО дубликатов на основе их текст, используя расстояние Левенштейн. Я уже удалял идентичные дубликаты, хешируя тексты твитов, но теперь хочу удалить тексты, которые идентичны, но имеют до 2-3 разных символов. Поскольку это подход O (n^2), я должен проверить каждый текст твита со всеми доступными другими. Вот мой код до сих пор:

int distance; 
for(Tweet tweet : this.tweets) { 
    distance = 0; 
    Iterator<Tweet> iter = this.tweets.iterator(); 
    while(iter.hasNext()) { 
     Tweet currentTweet = iter.next(); 
     distance = Levenshtein.distance(tweet.getText(), currentTweet.getText()); 
     if(distance < 3 && (tweet.getID() != currentTweet.getID())) { 
      iter.remove(); 
     } 
    } 
} 

Первая проблема заключается в том, что код бросает ConcurrentModificationException в какой-то момент и никогда не завершается. Второй: могу ли я сделать что-нибудь лучше, чем этот двойной цикл? Список твитов содержит около 400 000 твитов, поэтому мы говорим о 160 миллиардах итераций!

Answer 1

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

Что касается O(n^2) подхода: Там нет «лучше» алгоритма относительно его сложности, чем O(n^2) подхода. То, что я пытаюсь сделать, - это сравнение «все-ко всем», чтобы найти почти повторяющиеся элементы. Конечно, есть оптимизация для уменьшения общей емкости n, параллелизация параллельного анализа подписок исходного списка, но сложность всегда квадратична.

Answer 2

---

Это решение работает для вопроса в руке (до сих пор проходят с возможными входами), но нормальный набор операций для удаления дубликатов не будет работать, если вы не осуществить полный контракт для сравнения, чтобы вернуть 1,0 и -1 ,

---

Почему вы не выполняете свою собственную операцию сравнения с помощью Set, который может иметь только разные значения. Это будет O (n log (n)).

Set set = new TreeSet(new Comparator() { 
      @Override 
      public int compare(Tweet first, Tweet second) { 
       int distance = Levenshtein.distance(first.getText(), second.getText()); 
       if(distance < 3){ 
        return 0; 
       } 
       return 1; 
      } 
     }); 
     set.addAll(this.tweets); 
     this.tweets = new ArrayList<Tweet>(set);