Autor Beitrag
Christoph1972
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 690
Erhaltene Danke: 16


VS2015 Pro / C# & VB.Net
BeitragVerfasst: 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.

ausblenden C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
Int32[] liste = { 101112131617181920 }; //ist eigentlich eine list<T>, habe ich nur zum Demo so gemacht.


Int32 match = Result(15);


private Int32 Result(Int32 intValue)

    return result; //wäre in diesem Fall 16
}


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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 3803
Erhaltene Danke: 176

Arch Linux
Python, C, C++ (vim)
BeitragVerfasst: Do 12.11.09 01:15 
user profile iconChristoph1972 hat folgendes geschrieben Zum zitierten Posting springen:
Gibt es da was fertiges im FW
Jupp, List<T>.BinarySearch ist genau dafür da.
user profile iconChristoph1972 hat folgendes geschrieben Zum zitierten Posting springen:
ausblenden C#-Quelltext
1:
Int32[] liste = { 101112131617181920 }; //ist eigentlich eine list<T>, habe ich nur zum Demo so gemacht.					
Du darfst gerne
ausblenden C#-Quelltext
1:
var liste = new List<int> { 101112131617181920 };					

benutzen :zwinker: .

_________________
>λ=
Christoph1972 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 690
Erhaltene Danke: 16


VS2015 Pro / C# & VB.Net
BeitragVerfasst: Do 12.11.09 17:42 
Super, werde ich mir anschauen. DANKE!

_________________
Gruß
Christoph
Christoph1972 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 690
Erhaltene Danke: 16


VS2015 Pro / C# & VB.Net
BeitragVerfasst: 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! :zwinker:


Ich werde mal kurz versuchen eine eigene Idee umzusetzen, ist nur die Frage wie performant das wird.............

_________________
Gruß
Christoph
Christoph1972 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 690
Erhaltene Danke: 16


VS2015 Pro / C# & VB.Net
BeitragVerfasst: Do 12.11.09 19:54 
Ok, hier ist meine vorläufige Lösung:
ausblenden volle Höhe 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:
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.11455.11781.12342.32653.78964.147814.111110.112511.789612.555813.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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 3803
Erhaltene Danke: 176

Arch Linux
Python, C, C++ (vim)
BeitragVerfasst: Fr 13.11.09 00:27 
user profile iconChristoph1972 hat folgendes geschrieben Zum zitierten Posting springen:
Super, werde ich mir anschauen.
Und, weiterverfolgt :zwinker: ?
Anscheinend geht es aber auf einmal um unsortierte Listen...
Dann ist O(n) nicht zu schlagen, meine Stimme geht an
ausblenden C#-Quelltext
1:
liste.Where(x => x >= rtValue).Min()					

Deine etwas kompliziert gedachte ;) Lösung ist O(n * log n) durch List<T>.Sort.

user profile iconChristoph1972 hat folgendes geschrieben Zum zitierten Posting springen:
da Keys der SortedList ein Integer-Wert ist..
Stimmt dir die Hilfe darin zu ;) ?

_________________
>λ=
Christoph1972 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 690
Erhaltene Danke: 16


VS2015 Pro / C# & VB.Net
BeitragVerfasst: Fr 13.11.09 11:51 
Zitat:
Und, weiterverfolgt :zwinker: ?

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
ausblenden 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
{
    // Zusammenfassung:
    //     Stellt eine Auflistung von Objekten dar, auf die einzeln über einen Index
    //     zugegriffen werden kann.
    public interface IList<T> : ICollection<T>, IEnumerable<T>, IEnumerable
    {
        // Zusammenfassung:
        //     Ruft das Element am angegebenen Index ab oder legt dieses fest.
        //
        // Parameter:
        //   index:
        //     Der nullbasierte Index des Elements, das abgerufen oder festgelegt werden
        //     soll.
        //
        // Rückgabewerte:
        //     Das Element am angegebenen Index.
        //
        // Ausnahmen:
        //   System.ArgumentOutOfRangeException:
        //     index ist kein gültiger Index in der System.Collections.Generic.IList<T>.
        //
        //   System.NotSupportedException:
        //     Die Eigenschaft wird festgelegt, und die System.Collections.Generic.IList<T>
        //     ist schreibgeschützt.
        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. :zwinker:

_________________
Gruß
Christoph
Kha
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 3803
Erhaltene Danke: 176

Arch Linux
Python, C, C++ (vim)
BeitragVerfasst: Fr 13.11.09 17:38 
Irgendwie scheinen wir es geschafft zu haben, in jedem einzelnen Punkt aneinander vorbei zu reden :mrgreen: . 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 :oops: .
user profile iconChristoph1972 hat folgendes geschrieben Zum zitierten Posting springen:
Zitat:
Und, weiterverfolgt :zwinker: ?

Ja :-)
Bei der BinarySearch-Methode stehe ich echt auf dem Schlauch.

Ich kann es gerade leider nicht überprüfen:
ausblenden 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];
}

user profile iconChristoph1972 hat folgendes geschrieben Zum zitierten Posting springen:
Das Beispiel dzaebel.net/BinarySearch_Nearest.htm kann ich nicht auf Double umstellen,
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.
user profile iconChristoph1972 hat folgendes geschrieben Zum zitierten Posting springen:
da ILIst.Keys vom Typ Int ist
Äh, wie :gruebel: ? 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.

user profile iconChristoph1972 hat folgendes geschrieben Zum zitierten Posting springen:
Nein, das war und ist nur Mittel zum Zweck.
Soll heißen, sie liegen also unsortiert vor?

user profile iconChristoph1972 hat folgendes geschrieben Zum zitierten Posting springen:
Liste.Where gibt es beim FW 2.0 nicht.
Uff :D . Dann klau sie dir aus den Mono-Sourcen, ohne LINQ kann doch kein Mensch leben :mrgreen: .
Lässt sich aber immer als Schleife ausformulieren:
ausblenden C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
static double Nearest(List<double> list, double item)
{
  double result = 0// Der Faulheit halber, sonst ein isFirst-Flag benutzen
  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
ausblenden 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 :zwinker: .
user profile iconChristoph1972 hat folgendes geschrieben Zum zitierten Posting springen:
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 :nixweiss: .

user profile iconChristoph1972 hat folgendes geschrieben Zum zitierten Posting springen:
Überzeugen lasse ich mich nur durch ein Beispiel, das performanter und einfacher ist, als das von mir. :zwinker:
Jetzt bin ich aber gespannt :P .

_________________
>λ=
Christoph1972 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 690
Erhaltene Danke: 16


VS2015 Pro / C# & VB.Net
BeitragVerfasst: Fr 13.11.09 23:28 
Ok, ich bin überzeugt :-)

Ein fettes DANKE an dich!

ausblenden C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
static double Nearest(List<double> list, double item)
{
  double result = 0// Der Faulheit halber, sonst ein isFirst-Flag benutzen
  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. :D 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 3803
Erhaltene Danke: 176

Arch Linux
Python, C, C++ (vim)
BeitragVerfasst: Fr 13.11.09 23:52 
user profile iconChristoph1972 hat folgendes geschrieben Zum zitierten Posting springen:
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 :oops: .
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 ;) ):
ausblenden C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
static double Nearest(List<double> list, double value)
{
  double? nearest = null// Nullable<double> ersetzt double-Variable und bool-"Gesetzt"-Flag
  foreach (var item in list)
    if (!nearest.HasValue || Math.Abs(item - value) < Math.Abs(nearest.Value - item))
      nearest = item;
  return nearest.Value; // Bei list.Count == 0 knallt's...
}
Jupp, gefällt mir sogar besser als die for-Version :D .

_________________
>λ=
Christoph1972 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 690
Erhaltene Danke: 16


VS2015 Pro / C# & VB.Net
BeitragVerfasst: Sa 14.11.09 12:17 
Hallo Kha

Also, da stimmt was nicht.

ausblenden 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.222213.120.1,25 };//Ergebnisdaten
double[] datenbank ={101.513.621.0 }; //Referenzdaten 

void Identify()//suchen ob die Daten vorliegen, die in der Datenbank vorhanden sind
{
    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// Nullable<double> ersetzt double-Variable und bool-"Gesetzt"-Flag
    foreach (double item in list)
        if (!nearest.HasValue || Math.Abs(item - value) < Math.Abs(nearest.Value - item))
            nearest = item;
    return nearest.Value; // Bei list.Count == 0 knallt's...
}



produziert:

ausblenden 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:

ausblenden 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 :gruebel:

_________________
Gruß
Christoph
Kha
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 3803
Erhaltene Danke: 176

Arch Linux
Python, C, C++ (vim)
BeitragVerfasst: 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 :zwinker: ...

_________________
>λ=
Christoph1972 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 690
Erhaltene Danke: 16


VS2015 Pro / C# & VB.Net
BeitragVerfasst: So 15.11.09 21:53 
Hi,

so muss es sein:

ausblenden 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