Søg med binary search

er teksterne altid lige lange ?

hvis ja så kan du lave binær søgning på disk

eller bliver du nødt til at læse til memory og søge der - og det kan du naturligvis
ikke med store data mængder

eksempel

0 a
1 b
2 c
3 d
4 e
5 f
6 g
7 h
8 i
9 j

og

using System;
using System.Collections;
using System.IO;
using System.Text;

public class Mem
{
    private Hashtable data = new Hashtable();
    public void Load(string fnm)
    {
        StreamReader sr = new StreamReader(fnm);
        string line;
        while((line = sr.ReadLine()) != null)
        {
            string id = line.Substring(0,1);
            string txt = line.Substring(2,1);
            data.Add(id, txt);
        }
        sr.Close();
    }
    public string Find(string id)
    {
        return (string)data[id];
    }
}

public class OnDisk
{
    private FileStream fs;
    public void Open(string fnm)
    {
        fs = new FileStream(fnm, FileMode.Open, FileAccess.Read);
    }
    public string ReadRec(int rec)
    {
        fs.Seek(5 * rec, SeekOrigin.Begin);
        byte[] b = new byte[5];
        fs.Read(b, 0, 5);
        return Encoding.Default.GetString(b);
    }
    public string Find(string target)
    {
        int totrec = (int)((fs.Length + 2) / 5);
        int l = 0;
        int r = totrec - 1;
        int ix;
        while(l <= r) {
            ix = (r + l) / 2;
            string line = ReadRec(ix);
            string id = line.Substring(0,1);
            string txt = line.Substring(2,1);
            if(id == target) {
                return txt;         
            } else if(id.CompareTo(target) < 0) {
                l = ix + 1;
            } else {
                r = ix - 1;
            }
        }
        return null;
    }
    public void Close()
    {
        fs.Close();
    }
}

class MainClass
{
   
    public static void Main(string[] args)
    {
        Mem m = new Mem();
        m.Load(@"C:\test.dat");
        Console.WriteLine(m.Find("1"));
        Console.WriteLine(m.Find("2"));
        Console.WriteLine(m.Find("3"));
        Console.WriteLine(m.Find("4"));
        Console.WriteLine(m.Find("5"));
        Console.WriteLine(m.Find("6"));
        OnDisk od = new OnDisk();
        od.Open(@"C:\test.dat");
        Console.WriteLine(od.Find("1"));
        Console.WriteLine(od.Find("2"));
        Console.WriteLine(od.Find("3"));
        Console.WriteLine(od.Find("4"));
        Console.WriteLine(od.Find("5"));
        Console.WriteLine(od.Find("6"));
        od.Close();
    }
}

Teksterne er ikke lige lange, de første 8 tal er lige lange, men teksterne kan variere

så kan du ikke lave en binær søgning on disk !

hvor store data har du ? kan du læse det op i en Hashtable ?
(ligesom i min Mem klasse)

13000 linier, og ca 0,6mb data - ser på det med hashtablen

0.6 MB er nok en del på en PDA

måske kan du opbygge en index fil og bruge den til opslag ??

Hey arne, nu vil jeg forsøge mig med SQL database istedet, på CE'en. Du får de 30 point for dine løsninger ;)

ok