Søge algoritme, hvordan gør jeg det her?

Først og fremmest, så vil jeg bruge et eller andet ID3 bibliotek (eller implementere det selv, som jeg i sin tid valgte)...

så du slipper for det her hexeri hvad end det så er...:

    SearchAlbum = FilesArray.GetItemAt(j, 2).ToString();
    SearchArtist = FilesArray.GetItemAt(j, 3).ToString();
    SearchTitle = FilesArray.GetItemAt(j, 4).ToString();

(Det beibliotetk jeg selv er i gang med at skrive, introducere et MP3FileInfo Object, med ID3v1 og ID3v2 objecter, samt MP3Info (Frames, BitRate, Playtime ect. ect.), ID3v1 har så Album, Kunstner osv som Properties, det har ID33v2 også, men foruden dem så har ID3v2 en masse yderligere muligheder.

Så er man hvertfald fri for at hexe med stings og deres positioner i et Array...
Og istedet bruger man bare :

MP3FileInfo mp3fi = new MP3FileInfo("Path eller stream");
mp3fi.ID3v2.Artist // = Artist for filen...

Så vil jeg som det næste nok lave en eller flere Compares, som så sammenligner MP3'erne på de ting du gerne vil have dem til...

Det er bestemt ikke hekseri.. Det jeg først gør er at hente ALLE sange ind et array (FilesArray) med filstørrelse og ID3Tag info.. så jo, jeg HAR en ID3 tag klasse.

Grunden til det er: Lad os sige du har 40.000 mp3 filer (det har man selvfølgelig ikke ;))


Så skal du sammenligne med alle filer for hver fil du prøver at finde en match for. Derfor skal du hente ID3-tag info ud fra en fil 40.000 x 40.000 gange... Som jeg har lavet det, henter jeg det ind én gang, og så sammenligner det hele i arrayet. Hvilket går mindt 1000 gange hurtigere, bogstavligt talt

For det første, så skal du IKKE hente det ud 40.000 x 40.000 gange med det jeg beskriver, men 40.000 x 1 (Nødagtig det samme som du gør nu)...

Men istedet for at have noget der ligner en multidementionelt string array, så har du et object der giver mening...

For det andet, så duer det på ingen måde at hente så meget op i mem på en gang hvis du når der til, det giver i gennemsnit nok omkring 10 GB Hukommelsesforbrug...

og at løbe det igennem 40.000 x 40.000 er i alle tilfælde dumt, der kommer mine Compares ind i billedet da de vil kunne benyttes til sortering, så er vi da i det mindste nede på O(N Log N) og ikke O(N^2)...

Og dublet søgning efter sortering er O(N)...

Når du sortere, gøres det ikke med objeckterne selv, men på indices, så du får 3 tabeller ud af det...

Artist sorted, Album sorted, Title sorted

tvivler på at 40.000 stringe i et array fylder særlig meget?

Hmmm.... nej lyder også lidt vidt... kan godt være jeg er kommet til at glemme at dividere med 1024 en gang... lyder nok lidt sandsynligt.... og eller blande det sammen med de 40.000 x 40.000 eller noget...

hehe.. men, med den metode jeg bruger, kan du se en løsning til det? :)

Du bliver nød til at komme med mere kode omkring dit FilesArray haløj så...

Havde været så meget nemmere hvis det havde været et ID3 object, da jeg bare kunne have lavet nogle comparer ad hoc til det, samet slamet det sammen...

Filosofien bliver at du har din liste med alle informationerne i... dernæst har du 3 lister med indices i... dette er en sorteret indices tabel i forhold til de forskellige Album, title osv...

Så med en liste:

MP3'er:
[0] AlbumA, TitleB, ArtistC
[1] AlbumA, TitleD, ArtistC
[2] AlbumB, TitleE, ArtistA
[3] AlbumD, TitleC, ArtistB
[4] AlbumC, TitleA, ArtistD

SortedByAlbum
[0]= 0
[1]= 1
[2]= 2
[3]= 4
[4]= 3

SortedByArtist
[0]= 4
[1]= 0
[2]= 3
[3]= 1
[4]= 2

SortedByTitle
[0]= 2
[1]= 3
[2]= 0
[3]= 1
[4]= 4

hvis man er doven anlagt så laver man en masse MP3 objekter og gemmer
dem alle i 3 Hashtable's album, artist og title

arne v >>>

Ja så doven at

D:A:D - Lawrence Of Suburbia

overskriver

D:A:D - Scare Yourself

fordi kunstner navnet tilfældigvis er det samme...

ja artist er jo ikke unik  men så lav den til en Hashtable af ArrayList af de
samme MP3 objekter

Der er ingen af de 3 der er unikke, titel vil være det nærmeste, men da der er mange sange der er alvet remakes osv af, så er de ikke engang unikke...

Så vil mene det er lidt af et hax at begive sig ud i... men ok... man finder da hurtigt frem til det man vil

Ok... siden du ikke vil ud med spisfindighederne omkring din FilesArray, så er her et eksempel på hvordan du kan komme omkring det...

Det bygger dog i grove træk på det jeg tidligere har nævnt, nemlig at have objecter der holder informationerne omkring en MP3 frem for det jeg jo vil betegne som hexeri...

Jeg har ikke gidet at tage fat i nogen rigtig ID3 tag klasse, men derimod bare hurtigt strikket en lille klasse med de 3 inrformationer, Artist, Album og Title...

Dernæst har jeg lavet en Comparer der kan sammenligne på dem, hvor man kan angive hvad man vil sammmenligne på (dette kunne gøres med flere comparers, men det gad jeg ikke lige i dette eksempel)....

til sidst er der lavet en desideret collection til at holde alle MP3Info objecterne i... denne collection indeholder sortering for alle 3 atributter på MP3Info, nemlig Artist, Album og Title... og naturligvis kan man enumererer hen over disse sorterede lister....

So here goes:
_______________________________________________________________________________________

using System;
using System.Collections.Generic;

namespace MP3Fun
{
    public class MP3SortedCollection
    {
        private List<MP3Info> _mp3List;

        private MP3Info[] _innerList;
        private int[] _sortedByArtist;
        private int[] _sortedByAlbum;
        private int[] _sortedByTitle;

        private MP3Comparer comparer;

        public MP3SortedCollection()
            : this(256)
        {
        }

        public MP3SortedCollection(int capasity)
        {
            this._mp3List = new List<MP3Info>(capasity);
            this.comparer = new MP3Comparer();
        }

        public void Add(MP3Info item)
        {
            this._mp3List.Add(item);
        }

        #region _ Sorting _
        public void BuildSortedLists()
        {
            int len = this._mp3List.Count;
            this._sortedByArtist = new int[len];
            this._sortedByAlbum = new int[len];
            this._sortedByTitle = new int[len];

            for (int i = 0; i < len; i++)
                this._sortedByArtist[i] = this._sortedByAlbum[i] = this._sortedByTitle[i] = i;


            this.BuildSortedByArtist();
            this.BuildSortedByAlbum();
            this.BuildSortedByTitle();

            this._innerList = this._mp3List.ToArray();
        }

        private void BuildSortedByArtist()
        {
            this._innerList = this._mp3List.ToArray();
            this.comparer.ComparisonType = MP3Comparer.Comparison.Artist;
            Array.Sort(this._innerList, this._sortedByArtist, this.comparer);
        }

        private void BuildSortedByAlbum()
        {
            this._innerList = this._mp3List.ToArray();
            this.comparer.ComparisonType = MP3Comparer.Comparison.Album;
            Array.Sort(this._innerList, this._sortedByAlbum, this.comparer);
        }

        private void BuildSortedByTitle()
        {
            this._innerList = this._mp3List.ToArray();
            this.comparer.ComparisonType = MP3Comparer.Comparison.Title;
            Array.Sort(this._innerList, this._sortedByTitle, this.comparer);
        }
        #endregion

        public IEnumerable<MP3Info> SortedByArtist
        {
            get
            {
                for (int i = 0; i < this._mp3List.Count; i++)
                {
                    yield return this._innerList[this._sortedByArtist[i]];
                }
            }
        }

        public IEnumerable<MP3Info> SortedByAlbum
        {
            get
            {
                for (int i = 0; i < this._mp3List.Count; i++)
                {
                    yield return this._innerList[this._sortedByAlbum[i]];
                }
            }
        }

        public IEnumerable<MP3Info> SortedByTitle
        {
            get
            {
                for (int i = 0; i < this._mp3List.Count; i++)
                {
                    yield return this._innerList[this._sortedByTitle[i]];
                }
            }
        }

        public MP3Info GetByArtist(int index)
        {
            return this._innerList[this._sortedByArtist[index]];
        }

        public MP3Info GetByAlbum(int index)
        {
            return this._innerList[this._sortedByAlbum[index]];
        }

        public MP3Info GetByTitle(int index)
        {
            return this._innerList[this._sortedByTitle[index]];
        }

        public int FirstByArtist(string artist)
        {
            for (int i = 0; i < this._innerList.Length; i++)
                if (this.GetByArtist(i).Artist.Equals(artist, StringComparison.InvariantCultureIgnoreCase))
                    return i;
            return -1;
        }

        public int FirstByAlbum(string album)
        {
            for (int i = 0; i < this._innerList.Length; i++)
                if (this.GetByAlbum(i).Album.Equals(album, StringComparison.InvariantCultureIgnoreCase))
                    return i;
            return -1;
        }

        public int FirstByTitle(string title)
        {
            for (int i = 0; i < this._innerList.Length; i++)
                if (this.GetByTitle(i).Title.Equals(title, StringComparison.InvariantCultureIgnoreCase))
                    return i;
            return -1;
        }
    }

    public class MP3Comparer : IComparer<MP3Info>
    {
        public enum Comparison { Artist, Album, Title }
        private Comparison _comparisonType;

        public Comparison ComparisonType
        {
            get { return _comparisonType; }
            set { _comparisonType = value; }
        }

        public MP3Comparer()
        {
            this._comparisonType = Comparison.Artist;
        }

        public int Compare(MP3Info x, MP3Info y)
        {
            switch (this._comparisonType)
            {
                case Comparison.Artist:
                    //Console.WriteLine("Cmp Artist {0} to {1} : {2}", x.Artist, y.Artist, x.Artist.CompareTo(y.Artist));
                    return x.Artist.CompareTo(y.Artist);
                case Comparison.Album:
                    //Console.WriteLine("Cmp Album {0} to {1} : {2}", x.Album, y.Album, x.Album.CompareTo(y.Album));
                    return x.Album.CompareTo(y.Album);
                case Comparison.Title:
                    //Console.WriteLine("Cmp Title {0} to {1} : {2}", x.Title, y.Title, x.Title.CompareTo(y.Title));
                    return x.Title.CompareTo(y.Title);
            }
            return 0;
        }
    }

    public class MP3Info
    {
        private string _artist;
        private string _album;
        private string _title;

        public string Artist
        {
            get { return _artist; }
            set { _artist = value; }
        }

        public string Album
        {
            get { return _album; }
            set { _album = value; }
        }

        public string Title
        {
            get { return _title; }
            set { _title = value; }
        }

        public MP3Info()
        {

        }

        public MP3Info(string artist, string album, string title)
        {
            this._artist = artist;
            this._album = album;
            this._title = title;
        }
    }
}
______________________________________________________________________________________

Und eine bitchen test
______________________________________________________________________________________

using System;
using System.Collections.Generic;
using System.Text;

namespace MP3Fun
{
    class Program
    {
        static void Main(string[] args)
        {
            MP3SortedCollection col = new MP3SortedCollection();

            col.Add(new MP3Info("A", "D", "A"));
            col.Add(new MP3Info("A", "B", "C"));
            col.Add(new MP3Info("B", "A", "D"));
            col.Add(new MP3Info("B", "S", "C"));
            col.Add(new MP3Info("C", "B", "R"));

            col.Add(new MP3Info("A", "G", "W"));
            col.Add(new MP3Info("C", "X", "C"));
            col.Add(new MP3Info("A", "Z", "T"));
            col.Add(new MP3Info("A", "B", "G"));
            col.Add(new MP3Info("D", "H", "Y"));

            col.Add(new MP3Info("A", "W", "D"));
            col.Add(new MP3Info("A", "B", "U"));
            col.Add(new MP3Info("D", "Y", "O"));
            col.Add(new MP3Info("A", "B", "W"));
            col.Add(new MP3Info("D", "E", "P"));

            col.BuildSortedLists();

            foreach (MP3Info item in col.SortedByArtist)
                Console.WriteLine("{0} : {0}-{1}-{2}", item.Artist, item.Album, item.Title);
            Console.ReadLine();
            Console.WriteLine("----------");

            foreach (MP3Info item in col.SortedByAlbum)
                Console.WriteLine("{1} : {0}-{1}-{2}", item.Artist, item.Album, item.Title);
            Console.ReadLine();
            Console.WriteLine("----------");

            foreach (MP3Info item in col.SortedByTitle)
                Console.WriteLine("{2} : {0}-{1}-{2}", item.Artist, item.Album, item.Title);
            Console.ReadLine();
            Console.WriteLine("----------");


            int x;
            Console.WriteLine("Index for first album that starts with T: {0}",x = col.FirstByTitle("T"));
            Console.WriteLine("Complete information: {0}-{1}-{2}", col.GetByTitle(x).Artist, col.GetByTitle(x).Album, col.GetByTitle(x).Title);

        }
    }
}

Og der er masser af mullige forbedringer mm.....
Det var bare lige noget jeg slammede sammen på en ½ times tid...

Fx kunne det være optimalt at implementere en bedre form for FirstByX("Y") metode, der frem for linear probing, brugte Binær søning, eller man kunne implementere en lidt speciel form for binær søgning der udnøtede en forventning om en nogenlunde lige vægt mellem alle startbogstaver... (Det sidste var bare en lille pusig ide)

Og der er sikkert også et par andre ting... men det du kan lægge mærke til er at jeg her IKKE behøver nogen 40.000 x 40.000 læsninger på disken, da Artist, Album og Title er lagret i MP3Info objecktet...

Det er det samme jeg forventer mange ID3 biblioteker vil gøre (uden at vide det dog)... Hvilket (som jeg tidligere nævnte) gør at dit udsagn om, jeg citere:

""Derfor skal du hente ID3-tag info ud fra en fil 40.000 x 40.000 gange...""

Er fundamentalt forkert...

DOG er det jo ikke sikkert at alle ID3Tag biblioteker gør dette, Men det gør det jeg selv har lavet... (I en hvis extend, dvs tunge frames hentes ikke ud)...

Men HVIS det ID3 bibliotek du arbejder med ikke gør dette, så er det jo ikke svæere end at ligge sin egen skal oven på, som så kopiere de 3 værdiere op i 3 strings, samt holder en referance til de nødvendige resourcer (ID3 Objectet, samt Filen på disken)

jeg synes atdigt at det var nemmere at udnytte de indbyggede klasser i .NET

eksempel:

    public class MP3InfoCollection
    {
        private Dictionary<string,List<MP3Info>> artists = new Dictionary<string,List<MP3Info>>();
        private Dictionary<string,List<MP3Info>> albums = new Dictionary<string,List<MP3Info>>();
        private Dictionary<string,List<MP3Info>> titles = new Dictionary<string,List<MP3Info>>();
        public void Add(MP3Info mp3)
        {
            if(!artists.ContainsKey(mp3.Artist))
            {
                artists[mp3.Artist] = new List<MP3Info>();
            }
            artists[mp3.Artist].Add(mp3);
            if(!albums.ContainsKey(mp3.Album))
            {
                albums[mp3.Album] = new List<MP3Info>();
            }
            albums[mp3.Album].Add(mp3);
            if(!artists.ContainsKey(mp3.Title))
            {
                titles[mp3.Title] = new List<MP3Info>();
            }
            titles[mp3.Title].Add(mp3);
        }
        public List<MP3Info> FindByArtist(string artist)
        {
            if(artists.ContainsKey(artist))
            {
                return artists[artist];
            }
            else
            {
                return null;
            }
        }
        public List<MP3Info> FindByAlbum(string album)
        {
            if(albums.ContainsKey(album))
            {
                return albums[album];
            }
            else
            {
                return null;
            }
        }
        public List<MP3Info> FindByTitle(string title)
        {
            if(titles.ContainsKey(title))
            {
                return titles[title];
            }
            else
            {
                return null;
            }
        }
    }

Ja, men sådan kan man jo have forskellige meninger om hvad man syntes der er bedst...

Det er da klart at der er fordele og ulæmper ved begge scenarios, så er spørgsmålet hvad der er best for problem indehaveren...

Personligt tiltaler ordnede lister mig her ret meget... Men det hænger nok sammen med nogle af de ting jeg selv har arbejdet med omkring ID3 tags og MP3 filer...