4

我担心这不是一个简单的问题。我一直在思考这个问题的适当解决方案,并希望一群新的大脑对这个问题有更好的看法 - 让我们开始吧:

资料

我们在这里使用的是一个包含多个列的 csv 文件,与此问题相关的是:

  • 用户ID(整数,3~8位,存在多个同一个UserID的条目)LIST IS SORTED BY THIS
  • 请求参数)
  • Epoc (Long, epoc 时间值)
  • 点击网址(字符串)

我们在这里使用的数据中的每个条目都有这些属性的 !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 的条目

由于在数据收集过程中提到的异常,必须考虑以下几点:

如果 'Query' 和 'Epoc' 的两个条目共享相同的值,则必须检查列表中的以下元素是否符合这些条件,直到下一个条目具有这些属性之一的不同值。共享相同 Query 和 Epoc 值的条目组将被视为 -one- 条目,因此为了匹配一对,必须找到与“Query”值匹配的另一个条目。由于没有更好的名称,我们将共享相同 Query 和 Epoc 值的组称为“链”

现在它已经出来了,它变得更容易了,我们可以从中得到 3 种类型的配对组合:

  1. 入境与入境
  2. 入口&连锁
  3. 链条&链条

此处键入 1 仅表示列表中的两个条目对于“Query”共享相同的值,但对于“Epoc”不共享。

所以这总结了相等的查询对

还有不同查询对的情况,可以描述如下:

在我们匹配了相等的查询对之后,有可能存在没有与其他条目配对的条目,因为它们的查询不匹配 - 因为这个原因而没有与另一个条目匹配的每个条目都是集合的一部分称为“不同的查询”

该集合的成员必须在不遵循任何标准的情况下配对,但链仍被视为该对的一个条目。

至于匹配对,一般来说,可能没有冗余对——单个条目可以是 n 多个对的一部分,但两个单独的条目只能形成一对。

例子:

以下条目将成对出现

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/

在这个例子中,甜甜圈是一个链,因此对是(没有标题的行号):

  • 相等的查询对:(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
                    *
                    **/
                }
            }
        }

    }

因此,我尝试使用过多的循环来匹配这些对,导致运行时间非常长,直到这一点我才看到

好的,我希望我没有忘记任何重要的事情,稍后我会添加更多需要的信息如果您已经做到了这一点,感谢您的阅读 - 希望您有一个可以帮助我的想法

4

2 回答 2

1

使用 SQL 将数据导入数据库,然后执行查询。你的txt文件太大了;难怪需要这么长时间才能通过它。:)

于 2012-09-30T19:11:08.747 回答
0

首先,从每个链中删除除一个条目之外的所有条目。为此,请按(用户 ID、查询、纪元)排序,删除重复项。

然后,扫描排序列表。获取 (userid, query) 对的所有条目。如果只有一个,则将其保存在列表中以供以后处理,否则发出所有对。

对于您为以后处理而保存的给定用户的所有条目(这些是类型 2 和 3),发出对。

于 2012-09-30T18:10:11.740 回答