Ny forbedret datastruktur

Nu er der flere kombinationer end dem du lige har listet der :)

Men du kan løse det på flg. måde:

string[] Set1 = { "A", "B", "C", "D" };
string[] Set2 = { "1", "2", "3", "4" };

var result = from n in Set1
        from m in Set2
        select new{ n, m };

http://www.codeproject.com/KB/recipes/sets.aspx

Så findes der HashSet

Tiloverstående er der så en masse Linq Extensions, Exclude, Intersect, etc. ( sikker 100% på navnene, men de fleste muligheder er der )

mvh

Jeg er ikke ude efter at finde alle mulige kombinationer af 2 sets eller modellere sets generelt. Jeg vil selv definere, eksempelvis hvilke flyruter, der er mulige og så have mulighed for at tjekke om en given kombination er med.

Jeg vil gerne kunne noget a la

CleverStructure cs = new CleverStructure();
cs.Add("A", 1);
cs.Add("A", 2);
...
cs.Add("D", 4);

bool isValid = cs.ContainsCombination("C", 2);

Man kan løse det med
bool[][]
Dictionary<SourceAirport, List<DestinationAirport>
Dictionary<SourceAirport, Dictionary<DestinationAirport, bool>>

Jeg bruger den sidste, men da jeg ikke har brug for den inderste bool, så tænkte jeg om der findes en smartere struktur til at tjekke om 2 nøgler findes.

Hvad med kun at gemme 1 nøgle:

Hvis en lufthavn har et entydigt 3 bogstavs navn, kan du gemme rute i form af strings på 6 tegn.

Så kan du gemme disse rute-strings i en enkelt List eller lign.

Om de så skal gemmes 2 gange (begge veje) eller om der skal slås op 2 gange må afhænge af hvad dit program skal kunne.

@Tjans
Jeg går meget op i performance. Det skulle jeg nok have understreget. Søgning i en liste er O(n). Det kan ikke matche 2 dict versionen i lookup tid. Det vil desuden koste 2 string konkateneringer forud for hver lookup og man mister muligheden for at understøtte alle datatyper.

@Buzz og Janus
Hov hov, vent. Sorry jeg var for hurtig.

Har undersøgt HashSet yderligere. Det er tilsyneladende en ret ny collection. Jeg havde ikke fanget, at HashSet har lookup tiden O(1). Så er det jo en dictionary uden value og dermed kan det være løsningen på mine udfordringer

Dictionary<SourceAirport, HashSet<DestinationAirport>>

Man kan næppe opnå bedre performance end 2x O(1) opslag. Men det er dyrt hukommelsesmæssigt at have collections indlejret i collections. Det kan jeg nok godt leve med.

Med mindre andre kan reducere memory, men stadig have samme lookup ydelse.

Det ligner ikke at der kommer flere inputs.
Buuzzzz, jeg deler gerne point ud for at fremhæve HashSets.

svar.

Jeg er ny i C# og er her på eksperten for at lære mere, så jeg håber nogen vil forklare:

Vil et HashSet på ruterne ( som nævnt i #4 ), ikke være hurtigere, hvis man isoleret set skal slå op om en given rute findes?

Du kunne evt. definere en klasse til at holde to "lufthavne" og smide disse i et hashset:

public class CleverStructure
{
    private HashSet<Pair> pairs = new HashSet<Pair>();

    public void Add(object o1, object o2)
    {
        pairs.Add(new Pair(o1,o2));
    }

    public bool ContainsCombination(object o1, object o2)
    {
        return pairs.Contains(new Pair(o1,o2));
    }
}

public class Pair
{
    private object o1, o2;

    public Pair(object o1, object o2)
    {
        if( o1 == null || o2 == null )
            throw new ArgumentException("o1 or o2 null");
        this.o1 = o1;
        this.o2 = o2;
    }

    public override bool Equals(object obj)
    {
        Pair other = obj as Pair;

        if( other == null )
            return false;

        return Object.Equals(other.o1, this.o1)
            && Object.Equals(other.o2, this.o2);
    }

    // sakset herfra :http://stackoverflow.com/questions/263400/what-is-the-best-algorithm-for-an-overridden-system-object-gethashcode
    public override int GetHashCode()
    {
        unchecked // Overflow is fine, just wrap
        {
            int hash = 17;
            hash = hash * 23 + o1.GetHashCode();
            hash = hash * 23 + o2.GetHashCode();
            return hash;
        }
    }
}

#8 Tjens:
Før du kan slå ruterne op kræver det, at 2 lufthavne kombineres til 1 nøgle. Hvis lufthavne er repræsenteret ved eksempelvis strings, "CPH" og "LON", så skal du konkatenere de to strings inden du kan slå op.

Konkateneringen vil allokere plads til en nyt char array på 6 pladser(=tid+memory) og derefter iterere hver lufthavns string og kopiere chars over. String operationer kan være tidsrøvere. Herefter kan du slå op i O(1).

Jeg er ikke i tvivl om at 2 O(1) opslag vil være mere effektivt

@#9 UlrikM:
Jeg har ikke prøvet din tilgang, men jeg tvivler på, at den vil være hurtigere end Dict<HashMap>.

Du vil kunne undgå casting ved at kode begge klasse generiske. Lige nu kræver et kald til ContainsCombination
- 2 cast fra string til object
- en new operation(Pair)
- et kald til Pair.GetHashKey, som har 4 multiplikationer og 2 additioner, og 2 kald til GetHashKey.
- Et O(1) HashSet lookup

Lookup med Dict<HashSet> er 2xGetHashKey + O(1) Lookup

Tror der er en del forskel. Metode kald koster også performance. Jeg havde håbet at der fandtes slags udvidelse af HashSet, der fungerede med 2 nøgler, så man undgik indlejrede collections, der kræver en del memory.

// Generic version
public class CleverStructure<T1, T2>
{
    private HashSet<Pair<T1, T2>> pairs = new HashSet<PairPair<T1, T2>>();

    public void Add(T1 o1, T2 o2)
    {
        pairs.Add(new Pair<T1, T2>(o1,o2));
    }
...
}

Bare husk, du kan næsten helt sikkert lave det hele hurtigere i C++.

Hvorfor er det lige netop at det skal gå så hurtigt? Og hvad er hurtigt? Jeg er ret sikker på der er andre steder det kan optimeres bedre ...

Hvor mange opslag skal du kunne lave per/sekund? I hvor stort antal?

Det lyder som om du er uden i at optimere noget der måske ikke er et problem ... ? eller ved du allerede nu det er et problem? og så er vi faktisk tilbage hvor min kommentar startede ... der må være andre steder der kan optimeres mere.

mvh

@sandrasmurf: min løsning giver stadig O(1), omend det sikkert er en højere konstant. Men når jeg tilføjer egen implementering af GetHashCode og Equals skaber jeg noget kompleksitet, som du undgår i løsningen med et set for hver "lufthavn". Det kan dog også være lidt træls at jonglere med indlejrede hashsets, men det er måske et spørgsmål om at pakke det ind.. Hvor vidt Pair løsning har lavere hukommelsesforbrug, ved jeg ikke, men vil næsten tro det.

@buzzzz: Jep, det må vi ikke glemme: "Premature optimization is the root of all evil" :-)

Hmm, to objekter der i en equals returnerer true, bør vel også returnere den samme HashCode? Ellers ryger pointen vel lidt?

@johny: gør de ikke det?

Ah jo, læste lige koden forkert. My bad!

buzzz -> "Bare husk, du kan næsten helt sikkert lave det hele hurtigere i C++."
- det er faktisk ikke sikkert, kommer an på hvilke beregninger der skal udføres.

Anyway... det er som buzzz siger, hvor hurtigt skal det være?

Der findes omkring 3000 airport codes i verden, hvis blot halvdelen kan kombineres med hinanden må det give 4.500.000, hvilket jo ikke er det store.

Måden jeg ville løse det på er elementært, opret et dictionary eller hashset med de mulige kombinationer.

Jeg testede lige for sjov med 3.500.000 items i dictionary og hashset. Og lavede 1.000.000 opslag efterfølgende.

Har tager et dictionary omkring 6000 ticks og hashset omkring 7000 ticks. Så jeg ville vælge dictionary :), dels hurtigere, dels keyvalue based :)

Et tick svarer til 100 nanosekunder. Vi snakker altså omkring 600-700 microsekunder :-)

Min maskine. Processor    Intel(R) Core(TM) i7 CPU      Q 720  @ 1.60GHz, 1600 Mhz, 2 Core(s), 4 Logical Processor(s)

@janus_007
Derfor jeg også skrev "næsten" :-)

Men ingen ide om hvad for ting der er hurtigere af ting i .NET.

Præcis overstående ... jeg roder også med kæmpe Dicts og har aldrig oplevet problemer med performance endnu. Det er altid andre steder den er helt galt.

@ulrikm
Præcis ... en dum vane at komme ind i, men det er altid sjovt at vide hvad der reelt set også er hurtigst, i stedet for bare at tro på hvad man hører.

mvh

hey buzzz, hehe.. ja det så jeg også efter jeg trykkede send :) Kan nu heller ikke huske hvilke operationer :), stødte bare på det en dag jeg sad og hyggede :)
Jeg mener at have læst at performance imellem C# og C++ er ubetydelig lille, men at C++ har nogle mere præcise timerfunktioner og derfor er C++ stadig valget når det kommer til virkelig missionskritiske opgaver såsom rumfart, hjerteudstyr mv.

Måske andre her ved noget den påstand?

Der står lidt om det her: http://www.codeproject.com/KB/cs/CSharpVsCPP.aspx , men er det sandt?

Ja, der findes vist ikke nogen Realtime systemer i .NET ... men gør der med C++, og eneste jeg har kendskab til. .NET kører jo lidt når det har lyst :-) *heheh*

Og dens interne scheduler er vist lidt tilfældig, i forhold til andre systemer.

Men mon ikke Arne_v har en godt indspark her :-)

mvh

Jeg prøvede at undgå at rode mig ud i de store forklaringer, angående brugen og valgte derfor et letforståeligt lufthavnseksempel :-)

Indenfor operationsanalyse er det vigtigt at kunne modellere constraints og de vil ofte findes i en form a la lufthavnseksemplet. Der kan være mange forskellige constraints i en optimeringsmodel og de benyttes meget, derfor er det vigtigt, at implementeringen er fornuftig.

String konkatenering af de 2 nøgler er bestemt en mulighed, men jeg er sikker på, at den vil sløve algoritmen.

Jeg er ikke utilfreds med køretiden med Dict<Dict>. Overhovedet ikke. Essensen er såmænd bare, at jeg flere gange har spekuleret på om man kunne undgå den indlejrede bool i mit oprindelige eksempel. Og det kan man altså. Med HashSets.

Lidt blandede kommentarer omkring C++/C#/realtime:

1) I de fleste tilfaelde vil C# kode koere ca. lige saa hurtigt som C++ kode. Vel typisk mellem 5% hurtigere og 20% langsommere. Dette er for virkelige programmer - man kan faa stoerre forskelle med mikrobenchmarks, men det er ret uinteressant. Det er trivielt at vise at en JIT compiler teoretisk kan vaere lige saa hurtig som emn AOT compiler. Og praksis understoetter dette i rimelig grad.

2) Realtime programmer er ikke programmer som koerer meget hurtigt men programmer som koerer meget forudsigeligt. De mest gaengse styre systemer (Windows, standard Linux, diverse Unix etc.) er ikke super gode til realtime, fordi en process kan blive smidt ud til fordel for en anden process og dermed oedelaegge forudsigeligheden for den process som ryger ud. Der er specielle styre systemer som er rigtigt gode til real time. .NET er heller ikke godt til real time. Ikke p.g.a. manglende timer funktioner - findes de til C kan de jo DllImport'es. Men p.g.a. GC. Hvis man laver 100 iterationer i C++ og C# kunne man opleve:
C++ : alle 100 iterationer tager 11 ms
C# : 99 iterationer tager 10 ms mens 1 iteration tager 110 ms fordi GC koerer

Med hensyn til spoergsmaalet, saa er det bedste at vaelge en loesning som:
- har bedst mulige big O egenskaber
- giver en logisk kode

Umiddelbart vil jeg mene at det betyder:
int 0..N-1 keys => bool[][]
string keys => Dictionary<string, HashSet<string>>

Det er i 9999 ud af 10000 tilfaelde spild af tid at forsoege at optimere ud over dette.

To grunde:
1) det betyder sandsynligvis ikke noget for den faerdige apps totale performance
2) resultatet er uhyre environment specifikt

re 2) Selvom algoritme X er hurtigere end algoritme Y med .NET 2.0 32 bit paa en Core i7 saa kan Y sagtens vaere hurtigere end X med .NET 4.0 64 bit paa en Xeon. Kode har normalt en rimeligt lang levetid 5-20 aar og at optimere noget kode til den maskine udvikleren sidder ved idag er ret formaalsloest.