search

Home  >  Q&A  >  body text

php - 数据两两比较的高效算法?

数据库有十万条数据,比较的规则是,第一条和第二条后面的所有数据进行比较,第二条和后第三条后面的所有数据进行比较,以此类推。。。比较所有的数据.不想使用多重循环,想在一个循环内全部搞定,请问有比较好的算法吗?

PHPzPHPz2896 days ago515

reply all(3)I'll reply

  • 怪我咯

    怪我咯2017-04-10 17:31:45

    看到你的场景说是,找重复。
    SELECT id from table GROUP BY id HAVING COUNT(*)>1
    这样获取回来的就是含重复数据。

    如果是如题所说的两两比较,如果限定 "两两比较" 必然是 O(n^2),既然确定了时间复杂度,那么就不用算法效率了。剩下的就是考虑在那计算了。

    如果数据规模不够大,内存里计算完全可以了,前提是数据规模不大。

    详述场景~~~~~~~~~~~~~~~~

    reply
    0
  • ringa_lee

    ringa_lee2017-04-10 17:31:45

    先排序,后比较
    不建议在数据库中操作,最方便的就是把这10w 条数据取出来,放到 php 内存中来操作.

    代码如下

    $sql = "select id,data from table order by data asc";
    $result =  [
         0=>     ['id'=>3, 'data'=>1],
         1=>     ['id'=>1, 'data'=>2],
         2=>     ['id'=>4, 'data'=>2],
         3=>     ['id'=>5, 'data'=>2],
         4=>     ['id'=>2, 'data'=>5],
    ];
    //遍历小于
    //小于当前元素下标的元素
    //遍历大于
    //大于当前元素下标的元素
    //相同,有点复杂,代码如下
    $same = array();
    $current = 0;
    $next = $current + 1;
    //遍历一遍数组
    while(isset($result[ $next ])) {
        $data = $result[ $current ][ 'data' ];
        //如果当前元素值和下一个元素值一样,放到值数组中
        if ($data == $result[ $next ][ 'data' ]) {
            $same[ $data ][] = $result[ $next ];
            $next ++;
        }else{  //如果不一样,当前元素指向  当下标为$next的元素
            $current = $next;
            $next = $current+1;
        }
    }
    var_export($same);
    //结果
    array (
      2 => 
      array (
        0 => 
        array (
          'id' => 4,
          'data' => 2,
        ),
        1 => 
        array (
          'id' => 5,
          'data' => 2,
        ),
      ),
    )
    

    reply
    0
  • 天蓬老师

    天蓬老师2017-04-10 17:31:45

    有几个问题是需要注意的:
    1,数据要在内存中做排序或对比,不要在数据库内执行;
    2,两两比较的目的是什么?要从这10W+数据中取出最大的N个?还是做排序?建议在内存中用一个索引数组存储排序后的所有数据;
    3,排序算法使用快排;

    reply
    0
  • Cancelreply