Структура данных для хранения частотного числа попарных данных?

У меня есть таблица со сто 'записей, где поле сопряжено с аналогичным полем на основе идентификатора. Я хочу знать, какая хорошая структура данных для хранения частотных отсчетов за количество раз, когда пара появилась вместе, независимо от порядка, в котором они появились.

Пример данных:

<b>ID Feature</b> 5 F1 5 F2 6 F1 6 F2 7 F3 7 F1 7 F2 8 F1 9 F1 10 F1

Выходной сигнал выборки:

F1 F2 F3
F1 0 3 1
F2 3 0 1
F3 1 1 0

Одним из вариантов является сортировка всех функций и использование 2-мерного массива int для представления попарных данных, но затем 2/3 массива бесполезно/дублируется. Например, array[i][i] = 0 и array[i][j] = array[j][i]. Учитывая, что у меня есть сотни функций, такой подход не будет работать.

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

2 ответа

  1. Создайте класс, скажем, MyPair чтобы использовать для хэш-ключей, которые хранят пары ваших элементов, и переопределяет Object#equals(...)Object#hashCode()), чтобы порядок не имел значения (например, путем упорядочения лексикографически).

  2. Создайте Map чтобы сохранить частоту ваших пар.

class MyPair { public final String feature1; public final String feature2; public MyPair(String s1, String s2) { // Order features so comparison is order-independent. if (s1.compareTo(s2) <= 0) { // TODO: null check feature1 = s1; feature2 = s2; } else { feature1 = s2; feature2 = s1; } } @Override public int hashCode() { return (s1 + s2).hashCode(); // TODO: cache for performance. } @Override public boolean equals(that) { return (that instanceof MyPair) && (that.feature1.equals(this.feature1)) && (that.feature2.equals(this.feature2)); }
}

Затем можно использовать пары хэшей, как ожидалось:

Map<mypair,integer> freq = new HashMap<mypair,integer>();
MyPair pair1 = new MyPair("F1", "F2");
freq.get(pair1); // => null
freq.put(pair1, 1);
MyPair pair2 = new MyPair("F2", "F1");
freq.get(pair2); // => 1
</mypair,integer></mypair,integer>


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

import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
public class NeighborListExample { static class Pair { private String feature; private int cnt = 1; Pair(String feature) { this.feature = feature; } void incr() { cnt++; } @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + ((feature == null) ? 0 : feature.hashCode()); return result; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; Pair other = (Pair) obj; if (feature == null) { if (other.feature != null) return false; } else if (!feature.equals(other.feature)) return false; return true; } @Override public String toString() { return "(" + feature + ", " + cnt + ")"; } } static Map<string, list<pair="">> feature2neighbors = new HashMap<>(); private static int getId(Object[][] data, int i) { return ((Integer) data[i][0]).intValue(); } private static String getFeature(Object[][] data, int i) { return data[i][1].toString(); } private static void processFeatures(String[] array) { for (int i = 0; i < array.length; i++) { for (int j = 0; j < array.length; j++) { if (i != j) { List<pair> pairs = feature2neighbors.get(array[i]); if (pairs == null) { pairs = new LinkedList<>(); feature2neighbors.put(array[i], pairs); } Pair toAdd = new Pair(array[j]); int index = pairs.indexOf(toAdd); if (index == -1) { pairs.add(toAdd); } else { pairs.get(index).incr(); } } } } } static void print(Map<string, list<pair="">> feature2neighbors) { StringBuilder builder = new StringBuilder(); for (Map.Entry<string, list<pair="">> e : feature2neighbors.entrySet()) { builder.append(e.getKey()).append(" -> "); Iterator<pair> it = e.getValue().iterator(); builder.append(it.next().toString()); while(it.hasNext()) { builder.append(" ").append(it.next().toString()); } builder.append("\n"); } System.out.println(builder.toString()); } public static void main(String[] args) { //I assume that data is sorted Object[][] data = { { 5, "F1" }, // { 5, "F2" }, // { 6, "F1" }, // { 6, "F2" }, // { 7, "F3" }, // { 7, "F1" }, // { 7, "F2" }, // { 8, "F1" }, // { 9, "F1" }, // { 10, "F1" }, // }; List<string> features = new LinkedList<>(); int id = getId(data, 0); for (int i = 0; i < data.length; i++) { if (id != getId(data, i)) { processFeatures(features.toArray(new String[0])); features = new LinkedList<>(); id = getId(data, i); } features.add(getFeature(data, i)); } print(feature2neighbors); }
}
</string></pair></string,></string,></pair></string,>

Вне:

F1 -> (F2, 3) (F3, 1)
F3 -> (F1, 1) (F2, 1)
F2 -> (F1, 3) (F3, 1)

licensed under cc by-sa 3.0 with attribution.