找出多筆的亂數數字中,出現頻率最高的數字

edited 十月 2013 in 原創軟體分享區
今天逛CSDN討論區看到的..又是一個思考題.. (這是原文)http://topic.csdn.net/u/20100419/15/36F41EB1-F98B-4D47-B59F-AEA66F3A632D.html

蠻有意思的,我翻成PHP的題目
希望大家也來分享一下自己的寫法:

題目:找出多筆的亂數數字中,前10個出現頻率最高的數字?

大家共同的條件是
$randKey = 520;         // 亂數種子
$randNum = 10000000;    // 資料筆數
$randMax = 999;         // 最大數值
$randMin = 1;           // 最小數值

說明:
用上述的條件產生所有的亂數資料,並找出亂數資料中前10個出現頻率最高的數字。

如下列數據為計算結果:

[數字] => 出現次數

[736] => 10078
[275] => 10078
[198] => 10077
[566] => 10077
[855] => 10076
[244] => 10076
[691] => 10076
[896] => 10076
[912] => 10076
[469] => 10076
[948] => 10076
[972] => 10075
[797] => 10075
[160] => 10075
[240] => 10075
[358] => 10075
[248] => 10075
[305] => 10075
[286] => 10075
[359] => 10075
[255] => 10075
[636] => 10075
.....
.....
[221] => 9762
[779] => 9762
[36] => 9762
[377] => 9762
[287] => 9762
[698] => 9762
[743] => 9762
[899] => 9761
[503] => 9761
[171] => 9761
[658] => 9761
[51] => 9761
[246] => 9761
[487] => 9761

那麼前10應該是
[736][275][198][566][855][244][691][896][912][469]
這10組數字

下班前~我再把我的程式碼po出來~大家先試試看囉!

原始討論: http://twpug.net/x/modules/newbb/viewtopic.php?topic_id=5082

評論

  • edited 四月 2010
     <?php
    $randKey = 520;         // 亂數種子 
    $randNum = 10000000;    // 資料筆數 
    $randMax = 999;         // 最大數值 
    $randMin = 1;				//最小數值
    srand($randKey);
    $data=array();
    $top10=array();
    for($i=0;$i<$randNum;$i++)
    {
    	$buff=rand($randMin,$randMax);
    	if(isset($data[$buff]))
    	{
    		++$data[$buff];	
    	}
    	else
    	{
    		$data[$buff]=1;
    	}
    }
    for($j=0;$j<10;$j++)
    {
    	$buff_value=max($data);
    	$buff_key=array_search($buff_value,$data);
    	$buff_array=array($buff_key=>$buff_value);
    	array_push($top10,$buff_array);
    	unset($data[$buff_key]);
    }
    foreach($top10 as $key=>$val)
    {
    	foreach($top10[$key] as $keys=>$vals)
    	{
    		echo $keys.'->'.$vals.',';
    //736->10078,275->10078,198->10077,566->10077,855->10076,912->10076,896->10076,244->10076,691->10076,469->10076,
    	}
    }
    ?>
    
    感覺效率不彰..依題意做步驟解~應該可以用數學機率概念去偷吃
  • edited 四月 2010
    懶人法...便宜了人類辛苦了電腦XD
    <?
    $randKey = 520; // 亂數種子
    $randNum = 10000000; // 資料筆數
    $randMax = 999; // 最大數值
    $randMin = 1; // 最小數值
    srand($randKey);
    ini_set('memory_limit', '-1');//個人環境設定需求
    for ($i=1; $i<=$randNum; $i++){
    $randnum[]=rand(1,999);
    }
    $list=array_count_values($randnum);
    arsort($list);
    foreach ($list as $num => $val)
    {
    echo "$num => $val\n";
    if($show>8)break;
    else $show++;
    }
    ?>

    我有問題,在當出現次數一樣的時候,排序優先順序沒有規定要由數字大的或數字小的先排對吧?
  • edited 四月 2010
    我有問題,在當出現次數一樣的時候,排序優先順序沒有規定要由數字大的或數字小的先排對吧?
    嗯..聽說是這樣沒錯
    不過最後的排序結果會因為這個條件產生細微的差異(因為建立參考陣列時的演算方式不同)
  • edited 四月 2010
    呀~差點忘了~我先貼~要下班了!!
    <?php
    $randKey = 520;         // 亂數種子
    $randNum = 10000000;    // 資料筆數
    $randMax = 999;         // 最大數值
    $randMin = 1;           // 最小數值
    srand($randKey);
    for ($i = 0; $i < $randNum; $i++) {
        $r[rand($randMin, $randMax)] += 1;
    }
    arsort($r);
    echo "[".implode("][", array_slice(array_keys($r), 0, 10))."]";
    ?>
    
  • edited 四月 2010
    看到這行程式的邏輯...
    $r[rand($randMin, $randMax)] += 1;
    泡論壇果然是值得的!筆記!!
  • edited 四月 2010
    其實這是看個人堅持的問題,以我來說~這關念不對!這東西大有問題,會給php解釋器額外負擔
    for ($i = 0; $i < $randNum; $i++) {
    $r[rand($randMin, $randMax)] += 1;
    }
    就是
    for($i=0;$i<$randNum;$i++)
    {
    $buff=rand($randMin,$randMax);
    if(isset($data[$buff]))
    {
    ++$data[$buff];
    }
    else
    {
    $data[$buff]=1;
    }
    }
    差別只在一個isset()的判斷
    $r[rand($randMin, $randMax)] += 1;//如果該元素不在時,只能靠php解釋器讓他合理
    所以php解釋器做了什麼?例外處理
    1.元素不存在->建立元素
    2.後方運算元類型為算數運算元,定義型別為int,初始值設定為0
    那麼你覺得這些工作,是我們來幫php完成,讓php不要花額外資源去分析例外、除錯?
    還是為了寫短碼增加php的負擔?
    所以我測試時(全偵錯)就會....
    Notice: Undefined variable: r in D:\wamp\www\governmental\try.php on line 61
    Notice: Undefined offset: 981 in D:\wamp\www\governmental\try.php on line 61
    一整串例外處理的警示..囧
  • edited 四月 2010
    noon 提到的方式也許在迴圈之前加一個 $r = array_fill(1, 999, 0); 就可以避免 SoltyRain 提到的問題
  • edited 四月 2010
    嗯嗯..
    ~"~ 不過.. SoltyRain和我認知差異蠻大的...PHP是弱型態程式語言...而轉opcode前會剛好相反..因error_report設定才會有產生相對應的負擔

    SoltyRain 也有研究過 zend engine 嗎?
  • edited 四月 2010
    雖然是弱型別沒錯,不過呢...這也要是noon大這樣一定程度了解到php會做什麼的強者才適用
    比方說..
    <?php
    ecoh $var1;//結果是啥都沒有,那它幹麻不是0呢?
    echo ++$var2;//結果卻是1
    ?>
    其實我初學實也以為那種短碼才是撰碼的極致
    後來真正投入工作後~才覺不是這樣的,debug或之後維護或擴充簡直就是一個惡夢,沒有明確的變數起點
    另外值得一提的是函數中包函數在迴圈(或帶有迴圈性質的函數)中並不是好事,當然這要看環境,最好是設定一個變數去暫存
    可以避開php對記憶體的佔據,其實在一個程式執行後,php並不會將記憶體還給OS,而是保留等待其他進程,除非使用unset()
    雖然這個部份,多數情況下,看起來沒太大意義,但在某些應用會遇到一些記憶體資源問題
    可能因為這陣子都是做公司內部應用的程式,都在處理一堆數據的堆疊運算,比較容易對記憶體使用效率的問題敏感(一台server不是只處理amp)...囧
    理由其實只是不想讓大家使用起來不順~當mysql在遞迴查詢時..那真的好可怕 ~"~
    又因為那之中其實有些地方我可以用複寫php陣列的方式來處理(就是可以少SELECT幾次,那些是變動率很低的東西)
    相對會在php中小小的遞迴一下~所以呢..唉呀....小弟我已經不知所云了~ XD

  • edited 四月 2010
    嗯嗯~我贊成SoltyRain說法...可維護很重要。前幾天才看到
    軟體工程諺語: Q18: 隨便找個傻瓜都能寫出電腦能懂的程式碼。好的程式設計師寫人能看得懂的程式碼 - Martin Fowler.


    順便發個vld反組後的結果..大家可以思考看看.
    相同結果,前一個未宣告和後一個有宣告的狀況..(哈~哪位大大可以幫我排版嗎?字體關係~內容對齊不起來)
    Finding entry points
    Branch analysis from position: 0
    Return found
    filename:       /u02/programs/test1.php
    function name:  (null)
    number of ops:  4
    compiled vars:  !0 = $array
    line     # *  op                           fetch          ext  return  operands
    ---------------------------------------------------------------------------------
       2     0  >   ZEND_ASSIGN_DIM                                          !0, 1
             1      ZEND_OP_DATA                                             1, $1
       3     2    > RETURN                                                   1
             3*   > ZEND_HANDLE_EXCEPTION
    
    branch: #  0; line:     2-    3; sop:     0; eop:     3
    path #1: 0,
    


    Finding entry points
    Branch analysis from position: 0
    Return found
    filename:       /u02/programs/test.php
    function name:  (null)
    number of ops:  6
    compiled vars:  !0 = $array
    line     # *  op                           fetch          ext  return  operands
    ---------------------------------------------------------------------------------
       2     0  >   INIT_ARRAY                                       ~0
             1      ASSIGN                                                   !0, ~0
       3     2      ZEND_ASSIGN_DIM                                          !0, 1
             3      ZEND_OP_DATA                                             1, $3
       4     4    > RETURN                                                   1
             5*   > ZEND_HANDLE_EXCEPTION
    
    branch: #  0; line:     2-    4; sop:     0; eop:     5
    path #1: 0,
    
  • edited 四月 2010
    所以我的$show++也是類似的不良品+_+
    在這種小範例中玩玩或許還好,如果是較大型的程式日後要追蹤時這個變數可能會讓維護者一頭霧水(沒註解又找不到初始值...)
    獲益良多...
  • edited 四月 2010
    雖然沒有做初使值設定在內部的操作數量減少,但消耗的時間還是比較多,用下面這個程式碼做測試:
    <?php
    function microtime_float() {
        $time = explode(" ", microtime());
        return $time[1] . substr($time[0], 1);
    }
    
    $baseTime = microtime_float();
    $r = array_fill(1, 99999, 0);
    for ($i = 0; $i < 100000; $i++) {
        $r[$i] += 1;
    }
    echo (microtime_float() - $baseTime) . chr(10);
    
    $baseTime = microtime_float();
    for ($i = 0; $i < 100000; $i++) {
        $p[$i] += 1;
    }
    echo (microtime_float() - $baseTime) . chr(10);
    

    測試結果:
    [email protected]:~/tmp$ php -q test.php
    0.0802299976349
    0.186830043793
    [email protected]:~/tmp$ php -q test.php
    0.0694959163666
    0.169565916061
    [email protected]:~/tmp$ php -q test.php
    0.0795030593872
    0.17989397049
    [email protected]ntu:~/tmp$ php -q test.php
    0.0789070129395
    0.186314105988
    [email protected]:~/tmp$ php -q test.php
    0.081995010376
    0.17392706871
    [email protected]:~/tmp$ php -q test.php
    0.0666229724884
    0.237539052963
    

    測試環境:
    PHP 5.2.10-2ubuntu6.4 with Suhosin-Patch 0.9.7 (cli) (built: Jan  6 2010 22:41:56) 
    Copyright (c) 1997-2009 The PHP Group
    Zend Engine v2.2.0, Copyright (c) 1998-2009 Zend Technologies
        with Xdebug v2.0.4, Copyright (c) 2002-2008, by Derick Rethans
    

    error_reporting = E_ALL & ~E_NOTICE
  • edited 四月 2010
    說真的..這跟error_reporting無關
    一個沒有被宣告的變數,如何調用?(所以php會跑額外程式去幫你宣告,註冊一個變數到記憶體)
    弱型別僅僅是自轉型別...不存在的變數依然不存在~
    抄了一下kiang大的code,在頂端加上
    error_reporting(0);//關掉reporting
    0.057967901229858 0.24503302574158
    0.060437917709351 0.25438404083252
    0.05992603302002 0.25866413116455
    0.058640956878662 0.24766397476196
    單純這項測試中,有宣告至少比沒宣告快3~4倍
  • edited 四月 2010
    耶~討論區就該這樣~^^Y

    哈~SoltyRain你誤解我指的弱型別的義意喔!!
    我不是指強調自轉型別的事情...而是在OPCODE時期的"設計規則"要來"符合弱型別"....

    PHP程式碼分析後會轉OPCODE,在進入處理程序

    我大致拆 程式碼 => OPCODE => 執行 這三段

    程式碼 => OPCODE這段

    如我之前貼的opcode的部分,不論如何”都會有宣告”,所以並沒有”額外”程式去幫你宣告,這種問題。
    ZEND_ASSIGN_DIM
    ZEND_OP_DATA

    而PHP語法內的宣告,則是多出的ㄧ個額外資料:
    INIT_ARRAY => 初始陣列
    ASSIGN => 指派值

    而我指的弱型別的設計,只要辨識到有 ZEND_ASSIGN_DIM 就是有宣告,而不是一定非有 INIT_ARRAY 初始陣列 ASSIGN 指派值,才算是一個陣列。

    所以我提到"PHP是弱型態程式語言...而轉opcode會剛好相反"...

    因為SoltyRain提到 => 元素不存在->建立元素
    上面這一篇也提到 => 一個沒有被宣告的變數,如何調用?
             => php會跑額外程式去幫你宣告,註冊一個變數到記憶體
    所以我認為這部分和SoltyRain認知是有差異的..這樣的敘述像是跳過opcode


    接著,換 OPCODE => 執行

    如 kiang 提到的 =>雖然沒有做初使值設定在內部的操作數量減少,但消耗的時間還是比較多

    結論是....指派給初始值是很重要的...
  • edited 四月 2010
    假設array設置好了($test)

    $test=array_unique(array_combine(array_count_values($test),$test));
    arsort($test);
    //已完成操作
    //output
    for(i=0;i<10;i++)
    {
    echo test[$i].'<br />';

    }
  • edited 四月 2010
    如我之前貼的opcode的部分,不論如何”都會有宣告”,所以並沒有”額外”程式去幫你宣告,這種問題。 ZEND_ASSIGN_DIM ZEND_OP_DATA 而PHP語法內的宣告,則是多出的ㄧ個額外資料: INIT_ARRAY => 初始陣列 ASSIGN => 指派值
    是這樣沒錯,那麼為什差這麼多時間呢?(這真讓我感興趣~)
    INIT_ARRAY => 初始陣列 ASSIGN => 指派值
    
    這兩個東西並不單純~
    因為我們不定義"型別",ZE就會去查active符号表了(確實,用額外執行去敘述並不洽當,但確實做了額外工作)....
    "ASSIGN !0"<--這裡也產生了一個很大的差異了,表示op_type=IS_CV(原來..cv是 ZE2.1多出來的快取機制)
    指派值的同時,就建立了快取,確實以結論來說,有初始值很重要,但更重要的是~因為noon大又更清楚一些關念(笑
    期待下次增加實力的機會囉~
Sign In or Register to comment.