寻找统计字符串集合中配对出现次数的最快算法技术咨询

Great question! Your current nested loop + string-keyed dictionary approach works, but string concatenation for dictionary keys and redundant hash calculations are the biggest bottlenecks when dealing with large datasets. Let’s break down practical optimizations, starting with C# (your original language) and then covering other options.

Core Pain Points in the Original Approach #

• String keys like a;b require repeated memory allocation and garbage collection (GC), which slows things down significantly.
• If you’re iterating all pairs (including reverse duplicates like (a,b) and (b,a)), you’re doing twice the work you need to.

Optimized C# Implementation #

The key fixes here are:

1. Use ValueTuples instead of string keys to avoid allocation overhead.
2. Standardize pair order (e.g., always put the lexicographically smaller string first) to ensure unordered pairs map to the same key.
3. Minimize loop overhead by precomputing lengths and avoiding repeated property access.

Option 1: ValueTuple with String Ordering #

This is the simplest drop-in improvement:

var elements = new List<string> { "a", "b", "a", "c" }; // Example row elements
var pairCounts = new Dictionary<(string, string), int>();
int elementCount = elements.Count;

for (int i = 0; i < elementCount; i++)
{
    string s1 = elements[i];
    // Start j at i+1 to avoid duplicate pair checks (e.g., (i,j) and (j,i))
    for (int j = i + 1; j < elementCount; j++)
    {
        string s2 = elements[j];
        // Standardize the pair order to ensure unordered matches use the same key
        var key = string.Compare(s1, s2) < 0 ? (s1, s2) : (s2, s1);
        
        // Use TryGetValue to avoid double dictionary lookups
        if (pairCounts.TryGetValue(key, out int currentCount))
        {
            pairCounts[key] = currentCount + 1;
        }
        else
        {
            pairCounts[key] = 1;
        }
    }
}

// Optional: Convert back to string keys if needed
var stringKeyedCounts = pairCounts.ToDictionary(
    kvp => $"{kvp.Key.Item1};{kvp.Key.Item2}",
    kvp => kvp.Value
);

Option 2: Integer ID Mapping (For Large Datasets) #

If you’re dealing with thousands of unique strings, mapping each string to a unique integer ID reduces hash computation time even further:

var elements = new List<string> { "a", "b", "a", "c" };
var stringToId = new Dictionary<string, int>();
int nextId = 0;
var elementIds = elements.Select(s => 
{
    if (!stringToId.TryGetValue(s, out int id))
    {
        id = nextId++;
        stringToId[s] = id;
    }
    return id;
}).ToList();

var pairCounts = new Dictionary<(int, int), int>();
int idCount = elementIds.Count;

for (int i = 0; i < idCount; i++)
{
    int id1 = elementIds[i];
    for (int j = i + 1; j < idCount; j++)
    {
        int id2 = elementIds[j];
        var key = id1 < id2 ? (id1, id2) : (id2, id1);
        
        pairCounts[key] = pairCounts.TryGetValue(key, out int c) ? c + 1 : 1;
    }
}

// Optional: Map back to string keys
var stringKeyedCounts = pairCounts.ToDictionary(
    kvp => $"{stringToId.First(x => x.Value == kvp.Key.Item1).Key};{stringToId.First(x => x.Value == kvp.Key.Item2).Key}",
    kvp => kvp.Value
);

Parallel Processing (For Multiple Rows) #

If you’re processing hundreds/thousands of independent rows, use Parallel.ForEach to leverage multi-core CPUs (just use ConcurrentDictionary for thread safety):

var allRows = new List<string[]> { /* Your rows here */ };
var globalCounts = new ConcurrentDictionary<(string, string), int>();

Parallel.ForEach(allRows, row =>
{
    var localCounts = new Dictionary<(string, string), int>();
    int rowLength = row.Length;
    
    for (int i = 0; i < rowLength; i++)
    {
        string s1 = row[i];
        for (int j = i + 1; j < rowLength; j++)
        {
            string s2 = row[j];
            var key = string.Compare(s1, s2) < 0 ? (s1, s2) : (s2, s1);
            localCounts[key] = localCounts.TryGetValue(key, out int c) ? c + 1 : 1;
        }
    }
    
    // Merge local counts into global
    foreach (var kvp in localCounts)
    {
        globalCounts.AddOrUpdate(kvp.Key, kvp.Value, (_, existing) => existing + kvp.Value);
    }
});

Optimized Implementations in Other Languages #

Python #

Use tuples (hashable, no allocation overhead) and collections.defaultdict to simplify count tracking:

from collections import defaultdict

def count_unordered_pairs(elements):
    pair_counts = defaultdict(int)
    n = len(elements)
    for i in range(n):
        s1 = elements[i]
        for j in range(i + 1, n):
            s2 = elements[j]
            # Sort the pair to standardize the key
            key = tuple(sorted((s1, s2)))
            pair_counts[key] += 1
    return pair_counts

# Example usage
elements = ["a", "b", "a", "c"]
print(count_unordered_pairs(elements))
# Output: {('a', 'b'): 1, ('a', 'a'): 1, ('a', 'c'): 1, ('b', 'c'): 1}

Go #

Use a struct as the map key (Go 1.12+ supports struct keys) and standardize pair order:

package main

import "fmt"

type StringPair struct {
    First, Second string
}

func countUnorderedPairs(elements []string) map[StringPair]int {
    counts := make(map[StringPair]int)
    n := len(elements)
    for i := 0; i < n; i++ {
        s1 := elements[i]
        for j := i + 1; j < n; j++ {
            s2 := elements[j]
            var pair StringPair
            if s1 < s2 {
                pair = StringPair{s1, s2}
            } else {
                pair = StringPair{s2, s1}
            }
            counts[pair]++
        }
    }
    return counts
}

func main() {
    elements := []string{"a", "b", "a", "c"}
    fmt.Println(countUnorderedPairs(elements))
}

Key Optimization Takeaways #

• Avoid string keys: Use value types (ValueTuples, structs) or integer IDs to eliminate GC and allocation overhead.
• Standardize pair keys: Sort elements in each pair to ensure unordered matches map to the same key, cutting redundant work in half.
• Minimize loop overhead: Precompute lengths and avoid repeated dictionary lookups (use TryGetValue instead of ContainsKey + index access).
• Parallelize when possible: Use multi-core processing for independent rows, but only if the dataset is large enough to offset thread safety overhead.

内容的提问来源于stack exchange，提问作者dirtyw0lf