Re: [問題] 一維陣列中最長位置連續但數值相異的序列

[bleed1979 (十三)]

我又來了, 這表示有結果了

這題其實是ACM UVa的題目, 不用會員即可觀看的網址如下：
http://zerojudge.tw/ShowProblem?problemid=d194

不論題目的描述, 就是求位置連續但數值相異的最長序列

如果以上一篇文提到的演算法在 Zero Judge 是可以 AC 的, 因為測資不到100萬個
但在 ACM UVa 那裡就行不通了,而且限定的秒數比一般3.000秒還短的是2.000秒
所以怎麼傳怎麼TLE

先把演算法化為程式, 跑一次的程式碼如下：

==================================================
        scanf("%d", &snowflakes[0]);
        for(i = 0, j = 1, max = 0; j < n; ++j)
        {
            scanf("%d", &snowflakes[j]);

            for(x = j - 1; x >= i; --x)
            {
                if(snowflakes[j] == snowflakes[x])
                {
                    if(max < j - i)
                    {
                        max = j - i;
                    }
                    i = x + 1;
                    break;
                }
            }
        }
        if(max < j - i)
        {
            max = j - i;
        }

        printf("%d\n", max);
==============================================

i 表示左指標, j 表示右指標
內for迴圈就是循序查找的過程
最差的情況(全部相異) 1 + 2 + 3 + 4 + ... + n 次 = (n * (n + 1)) / 2
大概是O(n^2)的等級

而我說過如果用 C++ 的 STL 的 map 會有比較快的解答
演算法其實是一樣的, 程式碼如下：(snowflake 在此是 map<int, int> )
======================================================
                max = left = 0;
                snowflakes.clear();
                for (i = 1; i <= n; ++i)
                {
                        scanf ("%d", &flake);

                        if(left < snowflakes[flake])
                        {
                            left = snowflakes[flake];
                        }

                        snowflakes[flake] = i;

                        if(max < i - left)
                        {
                            max = i - left;
                        }
                }
                printf("%d\n", max);
======================================================

C++ 的寫法其速度大概是 C (上面那個程式) 的1/6倍 - 196ms 對 1.2s

而今天聽從網友的建議, 我去找了 C 的 Hash Table 的程式碼
經過修改後竟也過了, 其速度提升到 C++ 的1.5倍 - 276ms

可惜我改的這個程式是有版權的, 為表尊重不好公開, 但我提供網址如下：
Google 搜尋 "c hash table"
http://www.cl.cam.ac.uk/~cwc22/hashtable/

這個網站主人實作了 C 的 hash table 程式
我的作法是將 標頭檔 和 .c檔 全部加在一起, 並修改 search 的函式
search 函式在找到相同的 key 值會以新的 data 值替代舊的
所以傳入一個指標去存舊的 data 值, 才能實行 left 和 舊data值 比對的 if 敘述

另外要自行找 hash function
Google 搜尋 "hash function integer"
http://www.concentric.net/~Ttwang/tech/inthash.htm

我用的是 Robert Jenkins' 32 bit integer hash function 這個

附帶一提的是, 網站主人所寫的 destroy hash table 程式似乎有問題
上傳都是 runtime error, 最後我索性用註解槓掉, 不 free 記憶體的結果才過的
不過這樣不太好, 但至少運算過程其答案是對的


最後感謝大家提供的寶貴意見, 忙了一天總算有點收穫
接下來是好好研究這些程式的寫法


Bleed

--
World of bleed1979

http://bleed1979.myweb.hinet.net/


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 118.168.133.60
推 gba356:第二層迴圈只是要判斷「該數字有沒有在目前的序列中出現」
→ gba356:因此我想是可以用二分搜索樹或是雜湊表改進的，分別對應
→ gba356:O(NlgN) 和 O(N)，注意，當使用 STL map 的時候，可以很快
→ gba356:地找出上次出現的位置，因此左指針是可以直接跳轉的，
→ gba356:而其實做一個空間複雜度更好的雜湊表是不難的，可以用
→ gba356:unsigned int 實作，一個 bit 對應一個數字，保守估計
→ gba356:咦？我在說的應該是一對一的，可是一算之後發現
→ gba356:4,000,000 * 32 < 1e9，所以請忽略它（心算不好XDrz）
→ gba356:所以就用 BST 或是 STL map 或自己寫個雜湊吧~
推 FRAXIS:用Bit Vector記憶體夠嘛？
推 gba356:我不清楚 STL 的 Bit vector 耶，但是題目給 1e9 應該是要
→ gba356:我們用 O(NlgN) 的方法
→ bleed1979:好的, 我實作BST試試看, 有結果再上來po文
→ softwind:用 bit table, check value是否存在 為O(1)
推 gba356:問題是 10^9 開不到Q  Q
→ softwind:10^9 bits ~= 125Mbytes ?