從大量資料中找資料
有個檔案裏面有990,000,000筆數字，數字範圍為1~1,000,000,000，但是並沒有排序過，如果給一個數字X，寫個程式判斷X是否在其中。
這是某同學丟到 Facebook 的問題，我個人是覺得還挺有趣的
那以我的觀點來看，我會先詢問那些資料是否會重覆使用？不會的話，那我的想法一定是循序搜尋，反正就 O(n)，而如果會的話就有比較多的考量了，首先是以數值範圍而言，應該是長整數(佔4byte)，而 990,000,000 * 4 byte = 3,960,000,000 byte=3.69 GB 左右，雖然 RAM 有達到那樣的大小，可是一個程式跟系統索要接近 4G 的 RAM 似乎還挺誇張的，不過既然達得到，就能選擇「內部排序法」(EX: QuickSort) 或「外部排序法」(EX: MergeSort)，這兩個的最佳狀態時的時間成本約為 O(n log n)
再來搜尋有學過資結的第一個大概會想到的是二元搜尋法，但這只是數值，而且這麼大量的資料，我想透過插補排序法應該很不錯，所以以我的觀點會採用插補而非二元搜尋法，插補的時間成本約 O(log(log(n)))，我想這成本比二元搜尋法快非常多了
不過寫到這我又在想，有沒有可能像是把 1,000,000,000 切成 1,000 等份之類的，簡單來說像是以前四位來當作索引，這樣成本似乎會更低？(因為應該可以在排序時就開始排列；不過可能衍生的是 I/O 的成本！？)
我想先透過 N=1,000,000 ，資料型態為長整數的數值資料，並使用實體記憶體來想
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.IO;
using System.Security.Cryptography;
namespace BigNumberSearch
{
public partial class Form1 : Form
{
private static RNGCryptoServiceProvider rngp = new RNGCryptoServiceProvider();
private string FileName = Path.Combine(Application.StartupPath, "bigNumberList.dat");
private string FileName_TXT = Path.Combine(Application.StartupPath, "bigNumberList.txt");
private const int bucketNum = 0x3FF;
private byte[] data = new byte[8];
private string NumberBucket(int n)
{
return Path.Combine(Application.StartupPath, "bucket/num_" + n + ".dat");
}
public Form1()
{
InitializeComponent();
}
private void button1_Click(object sender, EventArgs e)
{
long n = Convert.ToInt64(textBox1.Text);
if (n > 1000000)
if (MessageBox.Show("你輸入的數值非常大，會花費相當多的時間與空間，確定要繼續？", "", MessageBoxButtons.YesNo) == System.Windows.Forms.DialogResult.No)
return;
System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
using (FileStream fs = new FileStream(FileName, FileMode.OpenOrCreate))
{
listBox1.Items.Insert(0, "產生亂數清單中");
sw.Start();
for (int i = 0; i < n; i++)
{
rngp.GetBytes(data);
data[7] = (byte)(data[7] & 0x7F);
// 上面的動作並非是取絕對值的動作，而是純粹將負號位元刪除
// 所以出來的值並不會相等於負數 * -1 的絕對值(正數因最高位元就是 0，所以不受影響)
fs.Write(data, 0, data.Length);
}
sw.Stop();
listBox1.Items.Insert(0, string.Format("產生完畢，共花費{0}時{1:00}分{2:00}.{3:000}秒",sw.Elapsed.Hours,sw.Elapsed.Minutes,sw.Elapsed.Seconds,sw.Elapsed.Milliseconds));
fs.Close();
}
MessageBox.Show("產生完畢");
}
private void button2_Click(object sender, EventArgs e)
{
listBox1.Items.Insert(0, "開始堆放資料進入盒子(檔案)裡");
FileStream[] writeFs = new FileStream[bucketNum + 1];
ushort num;
using (FileStream fs = new FileStream(FileName, FileMode.Open))
{
while(fs.Read(data, 0, data.Length) > 0)
{
num = BitConverter.ToUInt16(data, 0);
num &= bucketNum;
if (writeFs[num] == null)
writeFs[num] = new FileStream(NumberBucket(num), FileMode.OpenOrCreate);
writeFs[num].Write(data, 0, data.Length);
}
for (int i = 0; i < writeFs.Length; i++)
{
if(writeFs[i] != null)
{
writeFs[i].Close();
writeFs[i].Dispose();
writeFs[i] = null;
}
}
fs.Close();
}
MessageBox.Show("將數字堆放到盒子完畢");
}
private void button3_Click(object sender, EventArgs e)
{
// 排序盒子內的數字
string[] files = Directory.GetFiles(Path.Combine(Application.StartupPath, "bucket\\"), "num_*.dat");
List<long> numList = new List<long>();
foreach (var file in files)
{
numList.Clear();
string fullName = Path.Combine(Application.StartupPath, "bucket\\", file);
using(FileStream fs = new FileStream(fullName, FileMode.Open))
{
while (fs.Read(data, 0, data.Length) > 0)
{
numList.Add(BitConverter.ToInt64(data, 0));
}
listBox1.Items.Insert(0, "[File : " + file + "]共計" + numList.Count + "個項目被加到 List 中等待排序");
numList.Sort();
listBox1.Items.Insert(0, "數值資料被排序完畢，現在重新將資料寫回資料串流");
fs.Seek(0, SeekOrigin.Begin);
foreach(long num in numList)
{
data = BitConverter.GetBytes(num);
fs.Write(data, 0, data.Length);
}
fs.Close();
listBox1.Items.Insert(0, "資料重寫完畢");
}
}
}
private void button4_Click(object sender, EventArgs e)
{
listBox1.Items.Clear();
}
private void button5_Click(object sender, EventArgs e)
{
long n = Convert.ToInt64(textBox2.Text);
System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
byte[] data = BitConverter.GetBytes(n);
UInt16 num = BitConverter.ToUInt16(data, 0);
long dataNum;
num &= bucketNum;
string bucket = NumberBucket(num);
if (!File.Exists(bucket))
MessageBox.Show("該數值不在串列");
else
{
sw.Start();
using (FileStream fs = new FileStream(bucket, FileMode.Open))
{
while (fs.Read(data, 0, data.Length) > 0)
{
dataNum = BitConverter.ToInt64(data, 0);
if (dataNum == n)
{
sw.Stop();
listBox1.Items.Insert(0, string.Format("找到 {0} ，共計花費 {1} 時 {2} 分 {3}{4:000} 秒", n, sw.Elapsed.Hours, sw.Elapsed.Minutes, sw.Elapsed.Seconds, sw.Elapsed.Milliseconds));
MessageBox.Show("找到了，他有在裡面耶！XD");
fs.Close();
return;
}
}
}
listBox1.Items.Insert(0, string.Format("找不到 {0} ，共計花費 {1} 時 {2} 分 {3}{4:000} 秒", n, sw.Elapsed.Hours, sw.Elapsed.Minutes, sw.Elapsed.Seconds, sw.Elapsed.Milliseconds));
sw.Stop();
}
}
private void button6_Click(object sender, EventArgs e)
{
listBox1.Items.Insert(0, "開始進行檔案格式轉換");
using (FileStream fs = new FileStream(FileName, FileMode.Open))
{
FileStream fs2;
if (File.Exists(FileName_TXT))
fs2 = new FileStream(FileName_TXT, FileMode.Truncate);
else
fs2 = new FileStream(FileName_TXT, FileMode.CreateNew);
using (StreamWriter sw = new StreamWriter(fs2))
{
while (fs.Read(data, 0, data.Length) > 0)
{
long num = BitConverter.ToInt64(data, 0);
sw.WriteLine(string.Format("{0:0,0}", num));
}
}
fs2.Close();
fs2.Dispose();
fs2 = null;
fs.Close();
}
listBox1.Items.Insert(0, "檔案格式轉換完成");
}
}
}
/*
index array elements long
----- -------------- ----
8 00-00-00-00-00-00-00-00 0
00000000-00000000-00000000-00000000-00000000-00000000-00000000-00000000
5 FF-FF-FF-00-00-00-00-00 16777215
11111111-11111111-11111111-00000000-00000000-00000000-00000000-00000000
34 01-00-00-FF-FF-FF-FF-FF -16777215
00000001-00000000-00000000-11111111-11111111-11111111-11111111-11111111
17 00-CA-9A-3B-00-00-00-00 1000000000
00000000-11001010-10011010-00111011-00000000-00000000-00000000-00000000
0 00-36-65-C4-FF-FF-FF-FF -1000000000
00000000-00110110-01100101-11000100-11111111-11111111-11111111-11111111
21 00-00-00-00-01-00-00-00 4294967296
00000000-00000000-00000000-00000000-00000001-00000000-00000000-00000000
26 00-00-00-00-FF-FF-FF-FF -4294967296
00000000-00000000-00000000-00000000-11111111-11111111-11111111-11111111
53 AA-AA-AA-AA-AA-AA-00-00 187649984473770
10101010-10101010-10101010-10101010-10101010-10101010-00000000-00000000
45 56-55-55-55-55-55-FF-FF -187649984473770
01010110-01010101-01010101-01010101-01010101-01010101-11111111-11111111
59 00-00-64-A7-B3-B6-E0-0D 1000000000000000000
00000000-00000000-01100100-10100111-10110011-10110110-11100000-00001101
67 00-00-9C-58-4C-49-1F-F2 -1000000000000000000
00000000-00000000-10011100-01011000-01001100-01001001-00011111-11110010
37 FF-FF-FF-FF-FF-FF-FF-7F 9223372036854775807
11111111-11111111-11111111-11111111-11111111-11111111-11111111-01111111
9 00-00-00-00-00-00-00-80 -9223372036854775808
00000000-00000000-00000000-00000000-00000000-00000000-00000000-10000000
* ↑正負號看這byte第一位為1或0
*/
以上是我今天花一下午在實驗的程式碼，我利用到 RNGCryptoServiceProvider 來產生亂數然後我是採用最左邊的 2 byte取出來作 and 的位元運算，將亂數的值切成 1024 份
目前實驗起來 1024 份的大小還蠻平均的(我用 N=1,000,000)來算，原始的亂數檔為7mb多，作切割後每個檔案約 6~8 k
透過他作搜尋花費的時間非常的短(用 stopwatch 測試，都是 0 秒)，就算他是未排序過的值，所以最後我也沒進行任何排序的動作
如果數值更大的話可能還可以考慮排序完後採用插補搜尋之類的搜尋法，應該能更快速的去找到資料
或許有人有更好的想法，歡迎提出來共同討論！
留言
張貼留言