在串列串列中查找重復項-有解無憂

我有一個具有屬性的物件串列串列（比如說一個名稱和一個值）。

如果它是另一個串列的一部分，我想查找并洗掉重復的串列 - 它們的順序確實很重要。

偽代碼中的示例（我將其顯示為字串串列以使其更容易）：

List<List<String>>  = [
["1", "2", "3", "4", "5", "6", "7", "8"], 
["3", "4", "5", "6", "7", "8"],
["5", "6", "7", "8"],
["7", "8"]
]

在這種情況下，我想洗掉較短的串列，因為它們是較長/最多擴展串列的一部分。

我的課程可以這樣描述：

public static class MyObjectBig {
    private String startElem;
    private String endElem;
    private List<MyObjectOne> list;
    
    // constructors, getters, etc.
}

public static class MyObjectOne {
    private String name;
    private String value;

    // constructors, getters, etc.
}

大串列很大——比如 21,000 個元素，而小串列最多有 20 個元素，通常約為 10 個。

我有幾個想法，比如創建一個Map將第一項作為鍵并將所有串列作為值的方法。然后遍歷所有專案，檢查它是否存在，然后檢查下一個專案。但這很慢。

我會很感激任何提示或想法。

uj5u.com熱心網友回復：

假設equals/hashCode合同在中正確實作，MyObjectOne您可以定義一個輔助包裝類，該類將保存對原始MyObjectBig實體的參考并維護一個包含原始串列中每個元素的頻率HashMap的映射條目（因此，如果串列中可能存在重復的元素，在比較程序中會考慮它們）。MyObjectOne

這就是這樣的包裝類可能的樣子：

public static class BigObjectWrapper {
    private MyObjectBig bigObject;
    private Map<MyObjectOne, Long> frequencies;
    private int listSize;
    private int mapSize;
    private boolean isDuplicate;
    
    public BigObjectWrapper(MyObjectBig bigObject) {
        this.bigObject = bigObject;
        this.frequencies = bigObject.getList().stream()
            .collect(Collectors.groupingBy(
                Function.identity(),
                Collectors.counting()
            ));
        
        this.listSize = bigObject.getList().size();
        this.mapSize = frequencies.size();
    }
    
    public boolean contains(BigObjectWrapper other) {
        if (listSize < other.listSize || mapSize < other.mapSize) return false;
        
        return containsAll(other.frequencies);
    }
    
    private boolean containsAll(Map<MyObjectOne, Long> otherFrequencies) {
        
        return otherFrequencies.entrySet().stream() // frequency of each element in other map less or equal to frequency of this element
            .allMatch(entry -> frequencies.getOrDefault(entry.getKey(), 0L) >= entry.getValue());
    }
    
    public boolean isDuplicate() {
        return isDuplicate;
    }
    
    public void setDuplicate() {
        isDuplicate = true;
    }
    
    // getters, equals/hashCode implemented based on the size and set properties
}

現在，該演算法可以通過以下步驟實作：

創建包裝物件的串列。
將每個包裝器與其他包裝器進行比較。如果包裝器已經被證明是重復的，它將被跳過。此外，如果將包含較小集合的包裝物件與包含較大集合的包裝物件進行比較，則呼叫將立即終止回傳false（因此對資料進行排序沒有意義）。
從包裝物件生成一個新串列，MyObjectBig這些物件未被證明是重復的。

這就是實作的樣子：

List<MyObjectBig> source = List.of();
        
List<BigObjectWrapper> wrappers = source.stream()
    .map(BigObjectWrapper::new)
    .toList();
        
for (BigObjectWrapper wrapper : wrappers) {
    if (wrapper.isDuplicate()) continue;
    for (BigObjectWrapper next : wrappers) {
        if (next.isDuplicate()) continue;
        if (wrapper.contains(next)) next.setDuplicate();
    }
}
        
List<MyObjectBig> result = wrappers.stream()
    .filter(w -> !w.isDuplicate())
    .map(BigObjectWrapper::getBigObject)
    .toList();

注意：如果您不需要考慮一個較大的串列可以是另一個較大串列的一部分的情況，那么您可以將資料分成兩部分。然后作為第一步，只檢查較小的串列與較大的一次，作為第二步，檢查剩余的非重復的較小串列。

uj5u.com熱心網友回復：

更多的部分答案......這是我能想到的最愚蠢的解決方案。我相信O(N2 * M)其中 N 是父串列的長度，M 是子串列的長度。

我對這會有多慢很感興趣。在沒有任何證據的情況下簡單地假設愚蠢的解決方案將“太慢”通常是錯誤的。

我假設每個子串列中的值都是唯一的——使它們更像是有序集合——并且使用了可能值的池大小。子串列中可能的值越少 = 洗掉的子串列越多 = 速度越快。

在我的普通 CPU 上，20 個可能的值需要 100 毫秒，25 個可能的值需要 3 秒，40 個可能的值需要 8 到 10 秒。

不發布這個是因為我相信它是一個很好的解決方案，但它至少是一個作業基準（據我所知！），一個更復雜的解決方案應該被超越。

public static void main(String[] args) {
    List<List<String>> listOfList = randomData();

    long start = System.currentTimeMillis();
    Set<Integer> idxToRemove = new HashSet<>();
    for (int i = 0; i < listOfList.size() - 1;   i) {
        if (idxToRemove.contains(i)) continue;
        for (int j = i   1; j < listOfList.size();   j) {
            if (idxToRemove.contains(j)) continue;
            if (listOfList.get(i).containsAll(listOfList.get(j))) {
                idxToRemove.add(j);
            }
        }
    }
    idxToRemove.stream()
        .sorted(Comparator.reverseOrder())
        .mapToInt(i -> i)
        .forEach(listOfList::remove);
    long duration = System.currentTimeMillis() - start;
    System.out.println(idxToRemove.size());
    System.out.println("Took "   duration   "ms");
}

private static List<List<String>> randomData() {
    Random random = new Random();
    int mainLength = 21_000;
    int possibleValues = 40;

    List<List<String>> listOfList = new ArrayList<>(mainLength);
    for (int i = 0; i < mainLength;   i) {
        int subListSize = random.nextInt(5, 20);

        List<Integer> subList = new ArrayList<>(subListSize);
        while (subList.size() < subListSize) {
            int value = random.nextInt(possibleValues);
            if (!subList.contains(value)) {
                subList.add(value);
            }
        }
        listOfList.add(
            subList.stream().sorted().map(String::valueOf).collect(Collectors.toList())
        );
    }
    return listOfList;
}

uj5u.com熱心網友回復：

我會使用這樣的演算法：

按串列的長度對串列進行排序。您可以通過將內部串列分配給您排序的新外部串列來執行此操作，Collections.sort(List<T> newOuter, Comparator<? super T> c))其中 T 是您的內部串列List<String>和一個用于比較串列長度的自定義 Comparator。（String僅在此處使用，因為您將其用于示例，型別實際上并不重要。）
開始搜索最短的串列，首先在最長的串列中，然后在第二長的串列中，依此類推，直到您可以洗掉搜索的串列或搜索所有其他串列。然后，您不必觸摸那個最短的串列，它將被保留。重復第二個最短的串列，等等。

要在另一個串列中搜索串列：

在較長串列中搜索較短串列的第一個元素的索引。
當您發現并且較長串列的其余部分足夠長以包含較短串列時，您.subList從較長串列中獲取一個從找到的索引開始的較短串列長度。
然后，您可以將這些串列與比較，.equals()以確定較短的串列是否包含在較長的串列中。如果您的內部串列元素.equals()不足以支持此比較，您可以撰寫自己的 Comparator 并使用它來比較兩個串列。

如果在步驟 3 中未找到匹配項，您可以繼續在較長串列中搜索較短串列的第一個元素。由于List.indexOf沒有提供在哪個索引處開始搜索的引數，因此最好使用帶有索引的經典 for 回圈。.equals（如果不適合您，它還允許您使用自定義比較。）

要洗掉在另一個串列中找到的串列，您必須注意將其從原始外部串列中洗掉，而不是從排序版本中洗掉。

在考慮了一下之后，由于搜索串列的長度，我實際上不太確定在最長串列中開始搜索是否會平均節省您的時間。它可能有點取決于長度的分布。

另外我想警告您過早的優化：首先實作一個作業版本，然后使用分析器在您的代碼中查找優化將產生最大影響的位置。

轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/518397.html

標籤：爪哇列表重复

上一篇：為什么一個元素不列印？

下一篇：如何在資料框熊貓中插入串列