| Autor |
Beitrag |
Christoph1972
      
Beiträge: 690
Erhaltene Danke: 16
VS2015 Pro / C# & VB.Net
|
Verfasst: Mi 11.11.09 23:56
Hallo zusammen,
ich habe gerade eine Denksportaufgabe. Und zwar benötige ich eine Funktion die den Übergabeparameter( z.B. Integer) mit Zahlen aus einer Liste vergleicht. Der Rückgabewert soll ein Wert aus der Liste sein, der der übergebenen Zahl am nächsten kommt oder mit dieser übereinstimmt.
C#-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10:
| Int32[] liste = { 10, 11, 12, 13, 16, 17, 18, 19, 20 };
Int32 match = Result(15);
private Int32 Result(Int32 intValue) { return result; } |
Gibt es da was fertiges im FW, oder muss ich da selbst ran?
So, ich muss da erst mal drüber schlafen! Ich sage schon mal danke für euer Bemühen!
_________________ Gruß
Christoph
|
|
Kha
      
Beiträge: 3803
Erhaltene Danke: 176
Arch Linux
Python, C, C++ (vim)
|
Verfasst: Do 12.11.09 01:15
Christoph1972 hat folgendes geschrieben : | | Gibt es da was fertiges im FW |
Jupp, List<T>.BinarySearch ist genau dafür da.
Christoph1972 hat folgendes geschrieben : | C#-Quelltext 1:
| Int32[] liste = { 10, 11, 12, 13, 16, 17, 18, 19, 20 }; | |
Du darfst gerne
C#-Quelltext 1:
| var liste = new List<int> { 10, 11, 12, 13, 16, 17, 18, 19, 20 }; |
benutzen  .
_________________ >λ=
|
|
Christoph1972 
      
Beiträge: 690
Erhaltene Danke: 16
VS2015 Pro / C# & VB.Net
|
Verfasst: Do 12.11.09 17:42
Super, werde ich mir anschauen. DANKE!
_________________ Gruß
Christoph
|
|
Christoph1972 
      
Beiträge: 690
Erhaltene Danke: 16
VS2015 Pro / C# & VB.Net
|
Verfasst: Do 12.11.09 18:48
So, hier gibt es eine Lösung. Leider kann man mit dieser nur Integers vergleichen, eine Umstellung auf Double ist nicht möglich, da Keys der SortedList ein Integer-Wert ist. Bitte belehrt mich, das es doch geht!
Ich werde mal kurz versuchen eine eigene Idee umzusetzen, ist nur die Frage wie performant das wird.............
_________________ Gruß
Christoph
|
|
Christoph1972 
      
Beiträge: 690
Erhaltene Danke: 16
VS2015 Pro / C# & VB.Net
|
Verfasst: Do 12.11.09 19:54
Ok, hier ist meine vorläufige Lösung:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55:
| Double[] list = { 22.1145, 5.1178, 1.1234, 2.3265, 3.7896, 4.1478, 14.1111, 10.1125, 11.7896, 12.5558, 13.7822 };
private double FindDouble(double rtValue) { if (list.Length > 0) { List<double> lowerList = new List<double>(); List<double> upperList = new List<double>();
for (Int32 i = 0; i < list.Length; i++) { if (list[i] <= rtValue) lowerList.Add(list[i]); else upperList.Add(list[i]); }
lowerList.Sort(); upperList.Sort();
Double lowerValue = 0; Double upperValue = 0;
if (lowerList.Count > 0) { lowerValue = rtValue - lowerList[lowerList.Count - 1]; }
if (upperList.Count > 0) { upperValue = upperList[0] - rtValue; }
if (lowerValue <= upperValue) { if (lowerList.Count > 0) { return lowerList[lowerList.Count - 1]; } else return upperList[0]; } else { if (upperList.Count > 0) { return upperList[0]; } else return lowerList[lowerList.Count - 1]; } } else return 0; } |
Das funktioniert soweit.
Jetzt hätte ich gerne eure Meinung, in der Zwischenzeit gehe ich kurz 10Km laufen 
_________________ Gruß
Christoph
|
|
Kha
      
Beiträge: 3803
Erhaltene Danke: 176
Arch Linux
Python, C, C++ (vim)
|
Verfasst: Fr 13.11.09 00:27
Christoph1972 hat folgendes geschrieben : | | Super, werde ich mir anschauen. |
Und, weiterverfolgt  ?
Anscheinend geht es aber auf einmal um unsortierte Listen...
Dann ist O(n) nicht zu schlagen, meine Stimme geht an
C#-Quelltext 1:
| liste.Where(x => x >= rtValue).Min() |
Deine etwas kompliziert gedachte  Lösung ist O(n * log n) durch List<T>.Sort.
Christoph1972 hat folgendes geschrieben : | | da Keys der SortedList ein Integer-Wert ist.. |
Stimmt dir die Hilfe darin zu  ?
_________________ >λ=
|
|
Christoph1972 
      
Beiträge: 690
Erhaltene Danke: 16
VS2015 Pro / C# & VB.Net
|
Verfasst: Fr 13.11.09 11:51
| Zitat: | Und, weiterverfolgt ? |
Ja
Bei der BinarySearch-Methode stehe ich echt auf dem Schlauch. Das Beispiel dzaebel.net/BinarySearch_Nearest.htm kann ich nicht auf Double umstellen, da ILIst.Keys vom Typ Int ist
C#-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26:
| namespace System.Collections.Generic { public interface IList<T> : ICollection<T>, IEnumerable<T>, IEnumerable { T this[int index] { get; set; } |
| Zitat: |
Anscheinend geht es aber auf einmal um unsortierte Listen...
Dann ist O(n) nicht zu schlagen, meine Stimme geht an
liste.Where(x => x >= rtValue).Min()
|
Nein, das war und ist nur Mittel zum Zweck. Liste.Where gibt es beim FW 2.0 nicht.
| Zitat: |
Deine etwas kompliziert gedachte Lösung ist O(n * log n) durch List<T>.Sort.
|
Naja, ich finde meine Lösung ehr rudimentär als kompliziert
Sie gefällt mir sogar besser als die von dem Dzaebel, da sie einfacher zu verstehen ist und ganz einfach auf alle Zahlen-Typen umgestellt werden kann, was bei dem genannten Beispiel nicht der Fall ist.
| Zitat: |
da Keys der SortedList ein Integer-Wert ist..
Stimmt dir die Hilfe darin zu ?
|
Siehe den Code oben.
Ich finde die Hilfe zum Thema BinarySearch auch ehr mangelhaft als gut. Es gibt kein Beispiel zum vergleichen von Zahlen, nur Text wird behandelt.
Bei der Suche im Internet konnte ich leider auch nichts zum Thema finden, ausser zu Ganzzahlen.
Ich denke das ich bei meiner Lösung bleibe, da sie genau das macht was ich brauche. Überzeugen lasse ich mich nur durch ein Beispiel, das performanter und einfacher ist, als das von mir. 
_________________ Gruß
Christoph
|
|
Kha
      
Beiträge: 3803
Erhaltene Danke: 176
Arch Linux
Python, C, C++ (vim)
|
Verfasst: Fr 13.11.09 17:38
Irgendwie scheinen wir es geschafft zu haben, in jedem einzelnen Punkt aneinander vorbei zu reden  . Und ich merke erst jetzt, dass dieses "nächste" Element auch kleiner als der wert sein darf, da fallen meine generischen Lösungen leider weg  .
Christoph1972 hat folgendes geschrieben : | | Zitat: | Und, weiterverfolgt ? |
Ja
Bei der BinarySearch-Methode stehe ich echt auf dem Schlauch. |
Ich kann es gerade leider nicht überprüfen:
C#-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10:
| static double Nearest(List<double> sortedList, double item) { int i = sortedList.BinarySearch(item); if (i < 0) i = ~i; if (i == 0) return sortedList[i]; else return item - sortedList[i-1] < sortedList[i] - item ? sortedList[i-1] : sortedList[i]; } |
Zur Klarstellung, weil du das im gleichen Absatz erwähnst: Der Link verwendet kein List<t>.BinarySearch  . Ich glaube nicht, dass der Code für dein Problem überhaupt irgendeine Relevanz hat.
Christoph1972 hat folgendes geschrieben : | | da ILIst.Keys vom Typ Int ist |
Äh, wie  ? SortedList<TKey, TValue>.Keys ist vom Typ IList<TKey>. Du meinst wohl, dass der Indexer von IList<T> einen int-Parameter erwartet, aber da sehe ich das Problem nicht. Die ganzen Variablen wie idx bleiben natürlich bei int.
Christoph1972 hat folgendes geschrieben : | | Nein, das war und ist nur Mittel zum Zweck. |
Soll heißen, sie liegen also unsortiert vor?
Christoph1972 hat folgendes geschrieben : | | Liste.Where gibt es beim FW 2.0 nicht. |
Uff  . Dann klau sie dir aus den Mono-Sourcen, ohne LINQ kann doch kein Mensch leben  .
Lässt sich aber immer als Schleife ausformulieren:
C#-Quelltext 1: 2: 3: 4: 5: 6: 7: 8:
| static double Nearest(List<double> list, double item) { double result = 0; for (int i = 0; i++; i < list.Count) if (i == 0 || Math.Abs(list[i] - item) < Math.Abs(result - item)) result = list[i]; return result; } |
Korrigiert müsste es übrigens
C#-Quelltext 1:
| liste.Min(d => Math.Abs(d - rtValue)); |
heißen.
So, jetzt hast du sowohl für unsortierte als auch sortierte Listen eine Lösung, die ich mal ganz bescheiden als optimal bezeichne  .
Christoph1972 hat folgendes geschrieben : | | Ich finde die Hilfe zum Thema BinarySearch auch ehr mangelhaft als gut. Es gibt kein Beispiel zum vergleichen von Zahlen, nur Text wird behandelt. |
Es ändert sich ganz einfach ziemlich wenig, wenn man den Datentyp austauscht  .
Christoph1972 hat folgendes geschrieben : | Überzeugen lasse ich mich nur durch ein Beispiel, das performanter und einfacher ist, als das von mir.  |
Jetzt bin ich aber gespannt  .
_________________ >λ=
|
|
Christoph1972 
      
Beiträge: 690
Erhaltene Danke: 16
VS2015 Pro / C# & VB.Net
|
Verfasst: Fr 13.11.09 23:28
Ok, ich bin überzeugt
Ein fettes DANKE an dich!
C#-Quelltext 1: 2: 3: 4: 5: 6: 7: 8:
| static double Nearest(List<double> list, double item) { double result = 0; for (int i = 0; i++; i < list.Count) if (i == 0 || Math.Abs(list[i] - item) < Math.Abs(result - item)) result = list[i]; return result; } |
Genau das habe ich gesucht. (du hast noch mal eine Änderung vorgenommen, warum? foreach war doch ok....)
Diese Lösung ist erheblich eleganter als die von mir, dabei hat mir meine auch gefallen. An Ideen mangelt es mir wenigstens nicht.  Aber auf die Idee wäre ich nie und nimmer gekommen. Ich muss auch gestehen dass ich noch nicht wirklich durchschaut habe, warum das funktioniert. Werde ich mir morgen mal ausgeschlafen anschauen.
Ach ja, was ist ein isFirst-Flag?
_________________ Gruß
Christoph
|
|
Kha
      
Beiträge: 3803
Erhaltene Danke: 176
Arch Linux
Python, C, C++ (vim)
|
Verfasst: Fr 13.11.09 23:52
Christoph1972 hat folgendes geschrieben : | | du hast noch mal eine Änderung vorgenommen, warum? foreach war doch ok.... |
foreach sagt mir leider nicht, ob es sich um den ersten Schleifendurchlauf handelt, ich also noch gar kein Zwischenergebnis habe. Der Kommentar stammt noch von der foreach-Version, bitte einfach ignorieren  .
Bzw. um es kurz klar zu machen (zu Hause lässt sich einfach komfortabler tippen als auf einem 17-Zoller mit IE6, da fallen einem auch gleich viel bessere Variablennamen ein  ):
C#-Quelltext 1: 2: 3: 4: 5: 6: 7: 8:
| static double Nearest(List<double> list, double value) { double? nearest = null; foreach (var item in list) if (!nearest.HasValue || Math.Abs(item - value) < Math.Abs(nearest.Value - item)) nearest = item; return nearest.Value; } | Jupp, gefällt mir sogar besser als die for-Version  .
_________________ >λ=
|
|
Christoph1972 
      
Beiträge: 690
Erhaltene Danke: 16
VS2015 Pro / C# & VB.Net
|
Verfasst: Sa 14.11.09 12:17
Hallo Kha
Also, da stimmt was nicht.
C#-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22:
| double[] ergebnisse ={10.1, 1.2222, 13.1, 20.1,25 };double[] datenbank ={10, 1.5, 13.6, 21.0 }; void Identify(){ List<double> ergebnisListe = new List<double>(ergebnisse); List<double> datenbankListe = new List<double>(datenbank);
Debug.WriteLine("Ist" + " " + "Soll(aus DB)"); foreach (double value in datenbankListe) { Debug.WriteLine(Nearest(ergebnisListe, value) + " " + value); } } static double Nearest(List<double> list, double value) { double? nearest = null; foreach (double item in list) if (!nearest.HasValue || Math.Abs(item - value) < Math.Abs(nearest.Value - item)) nearest = item; return nearest.Value; } |
produziert:
Quelltext 1: 2: 3: 4: 5:
| Ist Soll(aus DB) 13,1 10 13,1 1,5 20,1 13,6 25 21 |
müsste aber so sein:
Quelltext 1: 2: 3: 4: 5:
| Ist Soll(aus DB) 10,1 10 1,2222 1,5 13,1 13,6 20,1 21 |
Es wird immer nur der nächste größere Wert angenommen. Wenn also 30.05 vorliegt und mit 30.04 & 30.1 verglichen wird, dann ist das Ergebnis 30.1, was falsch ist.
Und dabei habe ich heute nacht so gut geschlafen 
_________________ Gruß
Christoph
|
|
Kha
      
Beiträge: 3803
Erhaltene Danke: 176
Arch Linux
Python, C, C++ (vim)
|
Verfasst: Sa 14.11.09 14:58
Ja, kleiner Leichtsinnsfehler beim Umbenennen der Variablen. Ich bezeichne es einfach mal als Test, ob du den Code nachvollziehen kannst  ...
_________________ >λ=
|
|
Christoph1972 
      
Beiträge: 690
Erhaltene Danke: 16
VS2015 Pro / C# & VB.Net
|
Verfasst: So 15.11.09 21:53
Hi,
so muss es sein:
C#-Quelltext 1: 2: 3: 4: 5: 6: 7: 8:
| static double Nearest(List<double> list, double value) { double? nearest = null; foreach (double item in list) if (!nearest.HasValue || Math.Abs(item - value) < Math.Abs(nearest.Value - value)) nearest = item; return nearest.Value; } |
Aber ehrlich gesagt habe ich noch nicht raus warum das funktioniert. Morgen werde ich mal versuchen das mit Papier und Bleistift rauszufinden.
_________________ Gruß
Christoph
|
|
|