これは簡単な質問ではないのではないかと心配しています。私は長い間、この問題の適切な解決策について考えてきました。新鮮な頭脳がこの問題をよりよく理解してくれることを願っています。
データ:
ここで作業しているのは、複数の列を含む csv ファイルです。この問題に関連するものは次のとおりです。
- ユーザーID（3桁から8桁の整数、同じユーザーIDのエントリが複数存在）LIST IS SORTED BY THIS
- クエリ文字列）
- Epoc (ロング、エポック時間値)
- クリック URL (文字列)
ここで扱っているデータのすべてのエントリには、これらの属性の !null 値があります。
サンプルデータ:
SID,UID,query,rawdate,timestamp,timegap,epoc,lengthwords,lengthchars,rank,clickurl
5,142,westchester.gov,2006-03-20 03:55:57,Mon Mar 20 03:55:57 CET 2006,0,1142823357504,1,15,1,http://www.westchestergov.com
10,142,207 ad2d 530,2006-04-08 01:31:14,Sat Apr 08 01:31:14 CEST 2006,10000,1144452674507,3,12,1,http://www.courts.state.ny.us
11,142,vera.org,2006-04-08 08:38:42,Sat Apr 08 08:38:42 CEST 2006,11000,1144478322507,1,8,1,http://www.vera.org
注:「Epoc」の値が同じエントリが複数あります。これは、データの収集に使用されるツールが原因です。
注 2:リストのサイズは ~700000 です。
目標: 同じクエリを持つエントリのペアを一致させる
スコープ: 同じ UserID を共有するエントリ
前述のデータ収集プロセスの異常により、次の点を考慮する必要があります。
2 つのエントリが 'Query' と 'Epoc' に対して同じ値を共有する場合、次のエントリがこれらの属性の 1 つに対して異なる値を持つまで、リスト内の次の要素をこれらの基準についてチェックする必要があります。同じ Query 値と Epoc 値を共有するエントリのグループは、1 つのエントリと見なされるため、ペアを照合するには、「Query」値に一致する別のエントリを見つける必要があります。より適切な名前がないため、同じクエリとエポック値を共有するグループを「チェーン」と呼びましょう
これが出たので、少し簡単になりました。これから取得できるペア構成には 3 つのタイプがあります。
- エントリー＆エントリー
- エントリー＆チェーン
- チェーン＆チェーン
ここでタイプ 1 は、'Query' に対して同じ値を共有するが、'Epoc' に対しては共有しない、リスト内の 2 つのエントリを意味します。
したがって、これは等しいクエリペアを合計します
次のように説明できる別のクエリ ペアの場合もあります。
等しいクエリ ペアを一致させた後、クエリが一致しなかったために他のエントリとペアになっていないエントリが存在する可能性があります。別のエントリと一致していないすべてのエントリは、セットの一部であるためです。 「異なるクエリ」と呼ばれる
このセットのメンバーは、基準に従わずにペアにする必要がありますが、チェーンはペアの 1 つのエントリとして扱われます。
一般に、ペアの照合に関して、冗長なペアは存在しない可能性があります。単一のエントリは n 個のペアの一部になることができますが、2 つの個別のエントリは 1 つのペアしか形成できません。
例：
次のエントリをペアにする必要があります
UID,Query,Epoc,Clickurl
772,Donuts,1141394053510,https://www.dunkindonuts.com/dunkindonuts/en.html
772,Donuts,1141394053510,https://www.dunkindonuts.com/dunkindonuts/en.html
772,Donuts,1141394053510,https://www.dunkindonuts.com/dunkindonuts/en.html
772,raspberry pi,1141394164710,http://www.raspberrypi.org/
772,stackoverflow,1141394274810,http://en.wikipedia.org/wiki/Buffer_overflow
772,stackoverflow,1141394274850,http://www.stackoverflow.com
772,tall women,1141394275921,http://www.tallwomen.org/
772,raspberry pi,1141394277991,http://www.raspberrypi.org/
772,Donuts,114139427999,http://de.wikipedia.org/wiki/Donut
772,stackoverflow,1141394279999,http://www.stackoverflow.com
772,something,1141399299991,http:/something.else/something/
この例では、donuts はチェーンであるため、ペアは (ヘッダーなしの行番号) です。
- 等しいクエリ ペア:(1-3,9) (4,8) (5,6) (5,10) (6,10)
- 異なるクエリ ペア: (7,11)
問題への私の-失敗した-アプローチ:
これを解決するために開発したアルゴリズムは次のように機能します。
UserID の値が変わるまで、エントリのリストを繰り返します。
次に、同じ UserID を共有する反復された要素のみを含む別のリストに適用されます。
for (int i = 0; i < list.size(); i++) {
Entry tempI = list.get(i);
Boolean iMatched = false;
//boolean to save whether or not c1 is set
Boolean c1done = false;
Boolean c2done = false;
//Hashsets holding the clickurl values of the entries that form a pair
HashSet<String> c1 = null;
HashSet<String> c2 = null;
for (int j = i + 1; j < list.size(); j++) {
Entry tempJ = list.get(j);
// Queries match
if (tempI.getQuery().equals(tempJ.getQuery())) {
// wheter or not Entry at position i has been matched or not
if (!iMatched) {
iMatched = true;
}
HashSet<String> e1 = new HashSet<String>();
HashSet<String> e2 = new HashSet<String>();
int k = 0;
// Times match
HashSet<String> chainset = new HashSet<String>();
if (tempI.getEpoc() == tempJ.getEpoc()) {
chainset.add(tempI.getClickurl());
chainset.add(tempJ.getClickurl());
} else {
e1.add(tempI.getClickurl());
if (c1 == null) {
c1 = e1;
c1done = true;
} else {
if (c2 == null) {
c2 = e1;
c2done = true;
}
}
}
//check how far the chain goes and get their entries
if ((j + 1) < list.size()) {
Entry tempjj = list.get(j + 1);
if (tempjj.getEpoc() == tempJ.getEpoc()) {
k = j + 1;
//search for the end of the chain
while ((k < list.size())
&& (tempJ.getQuery().equals(list.get(k)
.getQuery()))
&& (tempJ.getEpoc() == list.get(k).getEpoc())) {
chainset.add(tempJ.getClickurl());
chainset.add(list.get(k).getClickurl());
k++;
}
j = k + 1; //continue the iteration at the end of the chain
if (c1 == null) {
c1 = chainset;
c1done = true;
} else {
if (c2 == null) {
c2 = chainset;
c2done = true;
}
}
// Times don't match
}
} else {
e2.add(tempJ.getClickurl());
if (c1 == null) {
c1 = e2;
c1done = true;
} else {
if (c2 == null) {
c2 = e2;
c2done = true;
}
}
}
/** Block that compares the clicks in the Hashsets and computes the resulting data
* left out for now to not make this any more complicated than it already is
**/
// Queries don't match
} else {
if (!dq.contains(tempJ)) { //note: dq is an ArrayList holding the entries of the differen query set
dq.add(tempJ);
}
}
if (j == al.size() - 1) {
if (!iMatched) {
dq.add(tempI);
}
}
}
if (dq.size() >= 2) {
for (int z = 0; z < dq.size() - 1; z++) {
if (dq.get(z + 1) != null) {
/** Filler, iterate dq just like the normal list with two loops
*
**/
}
}
}
}
したがって、過剰な量のループを使用してペアを一致させようとすると、実行時間が非常に長くなり、この時点まで見たことがないほど長くなります
重要なことを忘れていないことを願っています。後で必要な情報を追加します。ここまで読んでくれてありがとう。