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

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

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

<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.