[Vari] Context 2: Ricerca - Pagina 3

^TiGeRShArK^ · 20-07-2008, 03:12

Quote:

Originariamente inviato da gugoXX

Ecco, ci sono, per ora posto un output castrato.
Forse riesco a migliorare ancora un pochino, ma non sono convinto
Non metto il numero di letture da matrice per ora, per non svelare le carte.

Quella di Marco mi piace. Mi piacerebbe vederla all'opera sul matricione.
Quella di morskott dovrei vederla con piu' calma, vediamo anche i risultati e il numero di letture da matrice.
Consiglio anche a te di fare in Java la classe matrice, per far contare a lei il numero di volte che si fa una get di una cella.
Anche Tiger e 71104 mi piacerebbe vedere i risultati sul matricione.

si vabbè....ma così non vale

dicci almeno in che ordine di grandezza sei con il tuo algoritmo

io i limiti del mio con la ricerca binaria + o - li so, se vedo che il tuo è migliore già in partenza nemmeno mi metto ad implementarla la ricerca binaria che mi rompo le bolls

Comunque finora il + elegante postato mi sembra essere quello di marco...
X il + prestante in effetti ancora ho qualche dubbio...
a parte quello tuo che è completamente incognito

^TiGeRShArK^ · 20-07-2008, 03:18

Doppio..

^TiGeRShArK^ · 20-07-2008, 03:22

Triplo....

Vincenzo1968 · 20-07-2008, 06:05

Questa è, per il momento, la mia soluzione:

Codice:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace Matrix
{
    public class Matrix
    {
        private int _NumRows;
        private int _NumCols;

        int[,] matrix = null;

        public Matrix(int y, int x)
        {
            matrix = new int[y, x];
        }

        public Matrix(StreamReader sr)
        {
            string dimrow = sr.ReadLine();
            string[] dimstrings = dimrow.Split(',');

            if (dimstrings.Length != 2)
                throw new Exception("Head Error");

            _NumCols = int.Parse(dimstrings[0]);
            _NumRows = int.Parse(dimstrings[1]);

            matrix = new int[_NumRows, _NumCols];

            for (int row = 0; row < _NumRows; row++)
            {
                string rowstring = sr.ReadLine();
                string[] valoristringa = rowstring.Split(',');
                if (valoristringa.Length != _NumCols)
                    throw new Exception(string.Format("Record Error: {0}", row));
                var convertiti = valoristringa.Select((t, index) => new { index = index, val = int.Parse(t) });
                convertiti.ToList().ForEach(t => matrix[row, t.index] = t.val);
            }
        }

        public int GetCount = 0;

        public int GetLength(int dimension)
        {
            return matrix.GetLength(dimension);
        }

        public int NumRows
        {
            get
            {
                return _NumRows;
            }
        }

        public int NumCols
        {
            get
            {
                return _NumCols;
            }
        }

        public int this[int y, int x]
        {
            get
            {
                GetCount++;
                return matrix[y, x];
            }
        }
    }

    class Program
    {
        static public bool RicercaBinaria(Matrix mtx, int k, out int riga, out int colonna)
        {
            int b, a, m;
            int r = 0;

            riga = colonna = -1;

            while (r < mtx.NumRows)
            {
                b = 0;
                a = mtx.NumCols - 1;

                while (b <= a)
                {
                    m = (b + a) / 2;
                    if (k < mtx[r, m])
                        a = m - 1;
                    else if (k > mtx[r, m])
                        b = m + 1;
                    else
                    {
                        riga = r;
                        colonna = m;
                        return true; // Trovato
                    }
                }
                ++r;
            }

            return false;
        }

        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(@"C:\Scaricamenti\Temp\MatProva_250_200.txt");
            Matrix mt = new Matrix(sr);

            Console.WriteLine();

            int riga, colonna;

            int k = 0;

            if ( RicercaBinaria(mt, k, out riga, out colonna) )
                Console.WriteLine(k + " Trovato! Coord " + riga + ", " + colonna);
            else
                Console.WriteLine(k + " Non trovato!");

            k = 100;
            if (RicercaBinaria(mt, k, out riga, out colonna))
                Console.WriteLine(k + " Trovato! Coord " + riga + ", " + colonna);
            else
                Console.WriteLine(k + " Non trovato!");

            k = 32538;
            if (RicercaBinaria(mt, k, out riga, out colonna))
                Console.WriteLine(k + " Trovato! Coord " + riga + ", " + colonna);
            else
                Console.WriteLine(k + " Non trovato!");

            k = 20984;
            if (RicercaBinaria(mt, k, out riga, out colonna))
                Console.WriteLine(k + " Trovato! Coord " + riga + ", " + colonna);
            else
                Console.WriteLine(k + " Non trovato!");

            k = 32767;
            if (RicercaBinaria(mt, k, out riga, out colonna))
                Console.WriteLine(k + " Trovato! Coord " + riga + ", " + colonna);
            else
                Console.WriteLine(k + " Non trovato!");

            k = 32539;
            if (RicercaBinaria(mt, k, out riga, out colonna))
                Console.WriteLine(k + " Trovato! Coord " + riga + ", " + colonna);
            else
                Console.WriteLine(k + " Non trovato!");

            k = 26;
            if (RicercaBinaria(mt, k, out riga, out colonna))
                Console.WriteLine(k + " Trovato! Coord " + riga + ", " + colonna);
            else
                Console.WriteLine(k + " Non trovato!");

            k = 11672;
            if (RicercaBinaria(mt, k, out riga, out colonna))
                Console.WriteLine(k + " Trovato! Coord " + riga + ", " + colonna);
            else
                Console.WriteLine(k + " Non trovato!");

            k = 9790;
            if (RicercaBinaria(mt, k, out riga, out colonna))
                Console.WriteLine(k + " Trovato! Coord " + riga + ", " + colonna);
            else
                Console.WriteLine(k + " Non trovato!");

            k = 14089;
            if (RicercaBinaria(mt, k, out riga, out colonna))
                Console.WriteLine(k + " Trovato! Coord " + riga + ", " + colonna);
            else
                Console.WriteLine(k + " Non trovato!");

        }
    }
}

In pratica applico la ricerca binaria riga per riga. L'algoritmo dovrebbe avere, dunque, complessità O((log N)*M) nel caso peggiore(N = numero colonne, M = numero righe).

Spero di riuscire a postare una soluzione migliore.

Vincenzo1968 · 20-07-2008, 08:29

Credo di aver migliorato i tempi di ricerca utilizzando una lista concatenata.
Per la prima riga effettuo una ricerca lineare aggiornando la lista concatenata con gli indici delle colonne valide.

Dalla seconda riga in poi si effettua la ricerca binaria(escludendo le colonne calcolate al passo precedente).

Codice:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Diagnostics;

namespace Matrix
{
    public class Lista
    {
        public int colonna;
        public Lista next;
    }

    public class Matrix
    {
        private int _NumRows;
        private int _NumCols;

        int[,] matrix = null;

        public Matrix(int y, int x)
        {
            matrix = new int[y, x];
        }

        public Matrix(StreamReader sr)
        {
            string dimrow = sr.ReadLine();
            string[] dimstrings = dimrow.Split(',');

            if (dimstrings.Length != 2)
                throw new Exception("Head Error");

            _NumCols = int.Parse(dimstrings[0]);
            _NumRows = int.Parse(dimstrings[1]);

            matrix = new int[_NumRows, _NumCols];

            for (int row = 0; row < _NumRows; row++)
            {
                string rowstring = sr.ReadLine();
                string[] valoristringa = rowstring.Split(',');
                if (valoristringa.Length != _NumCols)
                    throw new Exception(string.Format("Record Error: {0}", row));
                var convertiti = valoristringa.Select((t, index) => new { index = index, val = int.Parse(t) });
                convertiti.ToList().ForEach(t => matrix[row, t.index] = t.val);
            }
        }

        public int GetCount = 0;

        public int GetLength(int dimension)
        {
            return matrix.GetLength(dimension);
        }

        public int NumRows
        {
            get
            {
                return _NumRows;
            }
        }

        public int NumCols
        {
            get
            {
                return _NumCols;
            }
        }

        public int this[int y, int x]
        {
            get
            {
                GetCount++;
                return matrix[y, x];
            }
        }
    }

    class Program
    {
        static public bool RicercaBinaria(Matrix mtx, int k, out int riga, out int colonna, out int passi)
        {
            Lista lst = null;
            Lista temp = null;
            int b, a, m;
            int r = 0;

            passi = 0;

            riga = colonna = -1;

            for (int j = 0; j < mtx.NumCols; j++)
            {
                passi++;
                if (k == mtx[0, j])
                {
                    riga = 0;
                    colonna = j;
                    return true;
                }
                else
                {
                    if (k > mtx[0, j])
                    {
                        if (lst != null)
                        {
                            temp = lst;
                            while (temp.next != null)
                                temp = temp.next;
                            temp.next = new Lista();
                            temp.next.colonna = j;
                            temp.next.next = null;
                        }
                        else
                        {
                            lst = new Lista();
                            lst.colonna = j;
                            lst.next = null;
                        }
                    }
                }
            }

            r = 1;
            while (r < mtx.NumRows)
            {
                passi++;
                if (lst == null)
                    return false;

                b = lst.colonna;
                a = mtx.NumCols - 1;

                while (b <= a)
                {
                    passi++;
                    m = (b + a) / 2;
                    if (k < mtx[r, m])
                        a = m - 1;
                    else if (k > mtx[r, m])
                        b = m + 1;
                    else
                    {
                        riga = r;
                        colonna = m;
                        return true; // Trovato
                    }
                }
                ++r;
                lst = lst.next;
            }


            b = 0;
            a = mtx.NumCols - 1;
            r = mtx.NumRows - 1;
            while (b <= a)
            {
                passi++;
                m = (b + a) / 2;
                if (k < mtx[r, m])
                    a = m - 1;
                else if (k > mtx[r, m])
                    b = m + 1;
                else
                {
                    riga = r;
                    colonna = m;
                    return true; // Trovato
                }
            }


            return false;
        }

        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(@"C:\Temp\MatProva_250_200.txt");
            Matrix mt = new Matrix(sr);

            Console.WriteLine();

            int riga, colonna;
            int passi;

            int k = 0;

            Stopwatch watch = new Stopwatch();
            watch.Start();

            if ( RicercaBinaria(mt, k, out riga, out colonna, out passi) )
                Console.WriteLine(k + " Trovato in " + passi + " passi. Coord " + riga + ", " + colonna);
            else
                Console.WriteLine(k + " Non trovato in " + passi + " passi.");

            k = 100;
            if (RicercaBinaria(mt, k, out riga, out colonna, out passi))
                Console.WriteLine(k + " Trovato in " + passi + " passi. Coord " + riga + ", " + colonna);
            else
                Console.WriteLine(k + " Non trovato in " + passi + " passi.");

            k = 32538;
            if (RicercaBinaria(mt, k, out riga, out colonna, out passi))
                Console.WriteLine(k + " Trovato in " + passi + " passi. Coord " + riga + ", " + colonna);
            else
                Console.WriteLine(k + " Non trovato in " + passi + " passi.");

            k = 20984;
            if (RicercaBinaria(mt, k, out riga, out colonna, out passi))
                Console.WriteLine(k + " Trovato in " + passi + " passi. Coord " + riga + ", " + colonna);
            else
                Console.WriteLine(k + " Non trovato in " + passi + " passi.");

            k = 32767;
            if (RicercaBinaria(mt, k, out riga, out colonna, out passi))
                Console.WriteLine(k + " Trovato in " + passi + " passi. Coord " + riga + ", " + colonna);
            else
                Console.WriteLine(k + " Non trovato in " + passi + " passi.");

            k = 32539;
            if (RicercaBinaria(mt, k, out riga, out colonna, out passi))
                Console.WriteLine(k + " Trovato in " + passi + " passi. Coord " + riga + ", " + colonna);
            else
                Console.WriteLine(k + " Non trovato in " + passi + " passi.");

            k = 26;
            if (RicercaBinaria(mt, k, out riga, out colonna, out passi))
                Console.WriteLine(k + " Trovato in " + passi + " passi. Coord " + riga + ", " + colonna);
            else
                Console.WriteLine(k + " Non trovato in " + passi + " passi.");

            k = 11672;
            if (RicercaBinaria(mt, k, out riga, out colonna, out passi))
                Console.WriteLine(k + " Trovato in " + passi + " passi. Coord " + riga + ", " + colonna);
            else
                Console.WriteLine(k + " Non trovato in " + passi + " passi.");

            k = 9790;
            if (RicercaBinaria(mt, k, out riga, out colonna, out passi))
                Console.WriteLine(k + " Trovato in " + passi + " passi. Coord " + riga + ", " + colonna);
            else
                Console.WriteLine(k + " Non trovato in " + passi + " passi.");

            k = 14089;
            if (RicercaBinaria(mt, k, out riga, out colonna, out passi))
                Console.WriteLine(k + " Trovato in " + passi + " passi. Coord " + riga + ", " + colonna);
            else
                Console.WriteLine(k + " Non trovato in " + passi + " passi.");

            watch.Stop();
            Console.WriteLine();
            Console.WriteLine("Tempo impiegato -> {0}", watch.ElapsedMilliseconds);

        }
    }
}

Questi sono i risultati:

gugoXX · 20-07-2008, 08:45

Ciao Vincenzo.
Per sapere quante volte hai letto una cella dalla matrice e' sufficiente utilizzare la proprieta'.
nomeMatrice.GetCount

Tenendo conto che dopo la lettura probabilmente vorrai anche resettare il conteggio con nomeMatrice.GetCount=0;

Comunque si' direi che ad occhio e' un O(n log m)
qualcosa in meno per la semplificazione iniziale, ma non vorrei appunto che tale semplificazione sia troppo controproducente. Prova a testare con la GetCount.

Per quanto riguarda me ho cercato di ottimizzare il mio algoritmo, ma mi e' venuto un incubo stile assembly che fa pena.
Ed inoltre ho solo peggiorato il numero di lettura, quindi ritorno sui miei passi.
E' un algoritmo semplice. Putroppo sento che e' migliorabile, ma non riesco proprio a trovare come.

71104 · 20-07-2008, 10:04

Quote:

Originariamente inviato da ^TiGeRShArK^

mmm..
ma non c'è un modo per inizializzare la matrice di booleani direttamente a true?
in quel modo hai complessità O(m*n) solo per l'inizializzazione di Auxiliary

azz, è vero

be' potrei invertire nell'algoritmo il significa di Auxiliary e così potrei accontentarmi di usare una matrice ausiliaria inizializzata interamente a false, ma mi sa che non faccio altro che spostare il problema dal mio codice al framework... il quale framework però dovrebbe comunque svolgere il compito in maniera più efficiente del mio codice visto che non è codice managed e quindi non effettua bound checking.

Quote:

Originariamente inviato da gugoXX

Posso gentilmente chiedervi se potete adoperare una classe matrice tipo questa
Oppure se comunque potete tenere il conto di tutte le volte che leggete un valore dalla matrice (anche per confronti, in qualsiasi caso)
cosi' possiamo poi confrontare i numeri di letture e in qualche modo dedurne la complessita' anche senza valutare l'algoritmo.

non sarebbe utile più di tanto, dovresti aggiungere il costo per costruire eventuali strutture ausiliarie; nel mio caso la matrice, nel caso di shinya l'heap.

gugoXX · 20-07-2008, 10:15

Ok.
Ipotizziamo pero' che il costo vero sia la lettura dalla Matrice.
Ipotizziamo che le celle siano remote e che leggere una cella costi 1 minuto, mentre invece qualsiasi altra operazione sia inifluente.
Solo per valutare la complessita' algoritmica, non la velocita' computazionale vera.

Per costruire l'Heap occorre conoscere il valore di tutte le celle remote, mentre la tua struttura ausiliaria e' locale. Inizializzare qualcosa a True o a False sarebbe comunque immediato.

Atlrimenti, se proprio come discorso non ti piace, prova a valutare se per te una Dictionary<Point,bool> inizialmente vuota sia sufficiente,
Dove popolare la Dictionary ogni volta che trovi un Point da gettarci dentro.
Se sceglierai cosi' fai attenzione agli operatori di eguaglianza. In particolare la
GetHashCode, che e' la funzione che viene usata dalle Dictionary.
che dovra' restituire un valore univoco per ciascun Point.

71104 · 20-07-2008, 10:51

ok, in effetti il discorso della matrice remota e delle strutture ausiliari locali ha senso.

ho sistemato un po' il mio codice e ho anche inserito un contatore che conta le chiamate; ipotizzando che ogni chiamata abbia un costo O(1) il contatore dovrebbe dare una stima della complessità dell'algoritmo secondo un certo input.

Codice:

    class MatrixTest
    {
        static int[,] matrix =
        {
            {1, 4, 7, 8, 9, 11},
            {2, 5, 8, 10, 11, 12},
            {5, 6, 9, 12, 14, 15},
            {7, 8, 12, 15, 17, 20},
            {8, 9, 17, 18, 19, 20},
        };

        static bool[,] auxiliary;
        static int counter;

        static bool Exists(int value, int x, int y)
        {
            if ((x >= matrix.GetLength(1)) || (y >= matrix.GetLength(0)))
            {
                return false;
            }

            if (auxiliary[y, x])
            {
                return false;
            }

            counter++;

            if (matrix[y, x] == value)
            {
                return true;
            }

            if (matrix[y, x] > value)
            {
                auxiliary[y, x] = true;
                return false;
            }

            if (Exists(value, x + 1, y))
            {
                return true;
            }

            if (Exists(value, x, y + 1))
            {
                return true;
            }

            auxiliary[y, x] = true;
            return false;
        }

        static bool Exists(int value)
        {
            auxiliary = new bool[matrix.GetLength(0), matrix.GetLength(1)];
            counter = 0;
            return Exists(value, 0, 0);
        }

        static void Main(string[] Arguments)
        {
            for (int i = 1; i <= 35; i++)
            {
                if (Exists(i))
                {
                    Console.WriteLine(i + " is present - " + counter + " calls");
                }
                else
                {
                    Console.WriteLine(i + " isn\'t present - " + counter + " calls");
                }
            }
        }
    }

a proposito, tanto per la cronaca quando a questo algoritmo viene chiesto di cercare un numero superiore al massimo presente (cioè un numero maggiore di matrix[n - 1, m - 1], n ed m dimensioni della matrice) vengono effettuate 30 chiamate. potrebbe essere considerato un difetto...

in effetti prima di eseguire qualunque calcolo non sarebbe insensato aggiungere un banale controllo su matrix[0, 0] e matrix[n - 1, m - 1] per vedere se il numero cercato può esistere nella matrice.

71104 · 20-07-2008, 11:21

i miei risultati col matricione:

Codice:

0 isn't present - 1 calls
100 isn't present - 6 calls
32538 isn't present - 50000 calls
20984 isn't present - 38115 calls
32767 isn't present - 50000 calls
32539 is present - 449 calls
26 is present - 1 calls
11672 is present - 250 calls
9790 is present - 11418 calls
14089 is present - 755 calls

certi fanno un po' schifo

shinya · 20-07-2008, 12:19

Ho rivisto un pò la soluzione con l'heap usando il file con la matriciona.
Mi sono accorto che l'heap può essere inizializzato una volta sola se i casi di test sono in ordine... quindi ho barato un pò, e ho ordinato l'array con i casi di test...

Codice:

import java.util.*;
import java.io.*;

public class Contest2 {
  public static void main(String[] args) throws Exception {
    String filename = "MatProva_250_200.txt";
    Scanner scanner = new Scanner(new File(filename));
    
    scanner.nextLine(); // salto la prima riga con le dimensioni
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
    while(scanner.hasNextLine()) {
      String line = scanner.nextLine();
      String[] numbers = line.split(",");
      for (String number : numbers) {
        pq.add(Integer.parseInt(number));
      }
    }
    
    int[] tests = {0, 100, 32538, 20984, 32767, 32539, 26, 11672, 9790, 14089};
    Arrays.sort(tests);
    
    for (int test : tests)
      search(pq, test);
  }
  
  private static void search(PriorityQueue<Integer> pq, int guess) {
    Integer head = pq.peek();
    
    if (head != null && guess < head) {
      System.out.println(guess + " not found in 1 step.");
      return;
    }
    
    int guessing = 0;
    while(head <= guess) {
      guessing++;
      head = pq.peek();
      
      if (head == null) break;
      if (head == guess) {
        System.out.println("Found " + guess + " in " + guessing + " steps.");
        return;
      }
      
      if (head < guess) pq.poll();
    }
    
    System.out.println(guess + " not found in " + guessing + " steps.");
  }
}

Output:

Codice:

0 not found in 1 step.
Found 26 in 1 steps.
100 not found in 4 steps.
Found 9790 in 11115 steps.
Found 11672 in 4380 steps.
Found 14089 in 6185 steps.
20984 not found in 16245 steps.
32538 not found in 12076 steps.
Found 32539 in 1 steps.
32767 not found in 2 steps.

Ordinare i casi di test è barare?

gugoXX · 20-07-2008, 12:35

Quote:

Originariamente inviato da shinya

Ho rivisto un pò la soluzione con l'heap usando il file con la matriciona.
Mi sono accorto che l'heap può essere inizializzato una volta sola se i casi di test sono in ordine... quindi ho barato un pò, e ho ordinato l'array con i casi di test...

Ordinare i casi di test è barare?

No, ovviamente ordinare i casi non e' barare.

Ma la soluzione cosi' non va bene.
Dovresti supporre di ricevere una Matrice dall'esterno, con determinate caratteristiche, e non di caricare l'heap e poi cominciare a contare gli accessi da li'.
Perche' per costruire l'heap devi comunque leggere tutta la matrice.
Ogni cella verra' letta almeno una volta.

Diciamo cosi', ogni volta che leggi una cella dalla matrice ci impeghi un minuto. Ma ce lo impieghi anche per costruire l'heap...
Una volta che hai costruito l'heap, e ti sei portato i valori in locale, e' tutto gratis. Ma il problema e' che anche per costruire l'heap avrai letto tutto. O(N * M).

E infatti c'e' un problema di base, non stai usando le 2 informazioni che i valori della matrice sono crescenti sulle righe e sulle colonne.
Se ti fosse stata data una matrice disordinata, avresti avuto le stesse performance. L'heap ordina tutto, indipendentemente dalla situazione di base. Ovvio che c'e' qualcosa che non va.

Inoltre se proprio devi leggere tutto fai che usare una hastable, non una Heap, cosi' in seguito in O(1) dirai se il valore c'e' o non c'e'.

marco.r · 20-07-2008, 12:57

Questo dopo aver trasformato la ricerca lineare iniziale in una ricerca binaria:

Codice:

def linearSearch( matrix, value, rowmin, colmin, rowmax,colmax ):
    i = rowmin
    j = colmin
    while i < rowmax and j < colmax and matrix(i,j) <= value:
        i+=1
        j+=1
    return [i,j]


def binarySearch( matrix, value, rowmin, colmin, rowmax, colmax ):
    size = min( rowmax-rowmin, colmax-colmin )
    if size < 5:
        return linearSearch(matrix,value,rowmin,colmin,rowmax,colmax)

    n = size/2

    current =  matrix( rowmin+n, colmin+n )
    next = matrix( rowmin+n+1, colmin+n+1 )
    if current <= value and next > value:
        return [rowmin+n,colmin+n]
    if current > value:
        return binarySearch( matrix, value, rowmin, colmin, rowmin+n,colmin+n)
    else:
        return binarySearch( matrix, value, rowmin+n, colmin+n, rowmax,colmax)

positionOfGreatestLowerOrEqualThan = binarySearch

(ho cambiato anche la notazione della matrice in matrix(i,j) per poter registrare gli accessi)

71104 · 20-07-2008, 17:47

ho fatto qualche modifica al mio algoritmo; ci credete se vi dico che ho ottenuto questi risultati?

Codice:

0 isn't present - 0 calls
100 isn't present - 252 calls
32538 isn't present - 201 calls
20984 isn't present - 354 calls
32767 isn't present - 0 calls
32539 is present - 200 calls
26 is present - 250 calls
11672 is present - 1 calls
9790 is present - 449 calls
14089 is present - 63 calls

marco.r · 20-07-2008, 18:04

ops. forse la mia versione ha un bug concettuale... meglio se ora controllo

^TiGeRShArK^ · 20-07-2008, 20:17

Quote:

Originariamente inviato da 71104

ho fatto qualche modifica al mio algoritmo; ci credete se vi dico che ho ottenuto questi risultati?

Codice:

0 isn't present - 0 calls
100 isn't present - 252 calls
32538 isn't present - 201 calls
20984 isn't present - 354 calls
32767 isn't present - 0 calls
32539 is present - 200 calls
26 is present - 250 calls
11672 is present - 1 calls
9790 is present - 449 calls
14089 is present - 63 calls

no, perchè è impossibile che tu riesca a sapere se un numero non è presente nella matrice senza leggere alcun valore..

a meno che non hai inventato l'algoritmo "nostradamus"

71104 · 20-07-2008, 20:21

l'ho ottimizzato ancora:

Codice:

0 isn't present - 0 calls
100 isn't present - 251 calls
32538 isn't present - 200 calls
20984 isn't present - 352 calls
32767 isn't present - 0 calls
32539 is present - 200 calls
26 is present - 250 calls
11672 is present - 1 calls
9790 is present - 449 calls
14089 is present - 63 calls

credo che meglio di così non si possa fare, il mio attuale algoritmo è di una semplicità disarmante

la complessità è O(N + M)

edit - e con queste ultime modifiche ho anche ridotto l'occupazione di memoria: ho tolto la matrice ausiliare, non serviva più.

71104 · 20-07-2008, 20:22

Quote:

Originariamente inviato da ^TiGeRShArK^

no, perchè è impossibile che tu riesca a sapere se un numero non è presente nella matrice senza leggere alcun valore..

a meno che non hai inventato l'algoritmo "nostradamus"

leggi bene, non c'è scritto "0 letture", c'è scritto "0 chiamate"; l'algoritmo in quel caso termina subito perché vede che il valore cercato è out-of-range.

gugoXX · 20-07-2008, 20:41

Mamma mia che risultatoni che leggo. E' dura qui. Tutti professionisti.
Marco.r, non ho capito come fai a gestire una matrice rettangolare con una sola riga e tante colonne. Mi spiego, potrebbe capitare che a forza di dividere il lavoro arrivi a dover leggere solo una riga. Mi sarei aspettato un qualcosa che incrementi solo sulla riga (o sulla colonna per il problema duale).

Mi sa che ho perso. Non sono tanto distante, ma non riesco a guadagnare di piu' se non facendo assunzioni non oneste.

Vi posto i miei risultati

Quote:

0 : Not Found
Letture da matrice: 11

100 : Not Found
Letture da matrice: 14

32538 : Not Found
Letture da matrice: 10

20984 : Not Found
Letture da matrice: 302

32767 : Not Found
Letture da matrice: 10

32539 : Found - Coords 249,199
Letture da matrice: 9

26 : Found - Coords 0,0
Letture da matrice: 10

11672 : Found - Coords 249,0
Letture da matrice: 454

9790 : Found - Coords 0,199
Letture da matrice: 1

14089 : Found - Coords 88,110
Letture da matrice: 169

Media di letture, su 1000 ricerche casuali con range 0 - 32539 : 125.54

E vi spiego il mio algoritmo.
A differenza di praticamente tutti voi, io sono partito dall'angolo in basso a sinistra.
Mi muovo lungo la riga, alla ricerca del primo valore immediatamente superiore al valore target. Una volta che lo trovo, sono sicuro che tutta la sottomatrice a sinistra non conterra' il target, essendo che saranno tutti valori inferiori al mio penultimo toccato, che era di sicuro inferiore al target.
A questo punto mi muovo verso l'alto, alla ricerca del primo valore minore del valore target. Non appena lo trovo sono sicuro che la sottomatrice basso-destra e' da escludere, essendo che contiene tutti valori maggiori o uguali al penultimo toccato, che era per definizione maggiore del valore target.
Ricomincio a muovermi verso destra, alla ricerca del primo valore superiore al target, poi di nuovo verso l'alto, alla ricerca del primo valore inferiore del target. etc.
In pratica mi muovo cercando di stare in equilibrio tra lavori immediatamente minori e valori immediatamente maggiori del target, lungo la "curva di potenziale", fino a che non lo trovo o fino a che non esco dalla matrice.

Questo algoritmo dovrebbe essere O(M + N) con il pregio che sono sicuro che il target lo trovero' in al piu' M+N mosse (ogni volta mi muovo o verso destra o verso l'alto)

Poi ho visto che cosi' stavo perdendo.
Allora ho dato un boost iniziale.
Alla prima ricerca mi muovo lungo la riga inferiore ( o lungo la colonna sinistra se il valore e' gia' > di quello target) con un divide et impera.
Ma solo per la prima ricerca, poi ho visto che per muoversi lungo la "curva di potenziale" era meglio procedere per passetti piccoli.

Quindi calcolare la compelssita' e' un casino, essendo che sono di fatto 2 algoritmi messi insieme.

Posto l'algoritmo senza divide et impera, che avra' valori un po' piu' alti, soprattuto nei limiti ( ma non tanto nei medi)

Codice:

public static Result Contains3(Matrix mat, int val)
{                
    int indx = 0;
    for (int indy = mat.DY-1; indy >= 0; indy--)
    {              
        do
        {
            int test = mat[indy, indx ];
            if (test == val) return new Result(val, true, indx, indy, mat.GetCount);
            if (test > val) break;
            indx++;
            if (indx == mat.DX) return new Result(val, false, -1, -1, mat.GetCount);
        } while (true);            
    }
    return new Result(val, false, -1, -1, mat.GetCount); ;
}

71104 · 20-07-2008, 20:47

Quote:

Originariamente inviato da gugoXX

A differenza di praticamente tutti voi, io sono partito dall'angolo in basso a sinistra.

io invece sono partito da quello in alto a destra

abbiamo avuto la stessa idea, solo che l'abbiamo applicata in modi opposti

se cambiassi un po' di cose nel mio algoritmo sono sicuro che avrei i tuoi stessi risultati.

Quote:

Mi muovo lungo la riga, alla ricerca del primo valore immediatamente superiore al valore target. Una volta che lo trovo, sono sicuro che tutta la sottomatrice a sinistra non conterra' il target, essendo che saranno tutti valori inferiori al mio penultimo toccato, che era di sicuro inferiore al target.
A questo punto mi muovo verso l'alto, alla ricerca del primo valore minore del valore target. Non appena lo trovo sono sicuro che la sottomatrice basso-destra e' da escludere, essendo che contiene tutti valori maggiori o uguali al penultimo toccato, che era per definizione maggiore del valore target.
In pratica mi muovo cercando di stare in equilibrio tra lavori minori e valori maggiori del target, lungo la "curva di potenziale", fino a che non lo trovo o fino a che non esco dalla matrice.

bla bla bla

sveglia, stai semplicemente visitando un albero binario di ricerca di altezza N+M

Quote:

Questo algoritmo dovrebbe essere O(M + N) con il pregio che sono sicuro che il target lo trovero' in al piu' M+N mosse (ogni volta mi muovo o verso destra o verso l'alto)

precisamente

posto il mio codice:

Codice:

        static bool Exists2(int value, int x, int y)
        {
            if ((x < 0) || (y >= matrix.GetLength(0)))
            {
                return false;
            }

            if ((value < matrix[y, 0]) || (value > matrix[matrix.GetLength(0) - 1, x]))
            {
                return false;
            }

            counter++;

            if (value < matrix[y, x])
            {
                return Exists2(value, x - 1, y);
            }
            else if (value > matrix[y, x])
            {
                return Exists2(value, x, y + 1);
            }
            else
            {
                return true;
            }
        }

        static bool Exists2(int value)
        {
            counter = 0;
            return Exists2(value, matrix.GetLength(1) - 1, 0);
        }

        static void CheckValue(int value)
        {
            if (Exists2(value))
            {
                Console.WriteLine(value + " is present - " + counter + " calls");
            }
            else
            {
                Console.WriteLine(value + " isn\'t present - " + counter + " calls");
            }
        }

        static void Main(string[] Arguments)
        {
            ReadMatrix();

            // not present
            CheckValue(0);
            CheckValue(100);
            CheckValue(32538);
            CheckValue(20984);
            CheckValue(32767);

            // present
            CheckValue(32539);
            CheckValue(26);
            CheckValue(11672);
            CheckValue(9790);
            CheckValue(14089);
        }

20-07-2008, 03:18	#42
^TiGeRShArK^ Senior Member Iscritto dal: Jul 2002 Città: Reggio Calabria -> London Messaggi: 12103	Doppio.. __________________ Ultima modifica di ^TiGeRShArK^ : 20-07-2008 alle 09:50.

20-07-2008, 03:22	#43
^TiGeRShArK^ Senior Member Iscritto dal: Jul 2002 Città: Reggio Calabria -> London Messaggi: 12103	Triplo.... __________________ Ultima modifica di ^TiGeRShArK^ : 20-07-2008 alle 09:50.

20-07-2008, 08:45	#46
gugoXX Senior Member Iscritto dal: May 2004 Città: Londra (Torino) Messaggi: 3692	Ciao Vincenzo. Per sapere quante volte hai letto una cella dalla matrice e' sufficiente utilizzare la proprieta'. nomeMatrice.GetCount Tenendo conto che dopo la lettura probabilmente vorrai anche resettare il conteggio con nomeMatrice.GetCount=0; Comunque si' direi che ad occhio e' un O(n log m) qualcosa in meno per la semplificazione iniziale, ma non vorrei appunto che tale semplificazione sia troppo controproducente. Prova a testare con la GetCount. Per quanto riguarda me ho cercato di ottimizzare il mio algoritmo, ma mi e' venuto un incubo stile assembly che fa pena. Ed inoltre ho solo peggiorato il numero di lettura, quindi ritorno sui miei passi. E' un algoritmo semplice. Putroppo sento che e' migliorabile, ma non riesco proprio a trovare come. __________________ Se pensi che il tuo codice sia troppo complesso da capire senza commenti, e' segno che molto probabilmente il tuo codice e' semplicemente mal scritto. E se pensi di avere bisogno di un nuovo commento, significa che ti manca almeno un test. Ultima modifica di gugoXX : 20-07-2008 alle 08:56.

20-07-2008, 10:15	#48
gugoXX Senior Member Iscritto dal: May 2004 Città: Londra (Torino) Messaggi: 3692	Ok. Ipotizziamo pero' che il costo vero sia la lettura dalla Matrice. Ipotizziamo che le celle siano remote e che leggere una cella costi 1 minuto, mentre invece qualsiasi altra operazione sia inifluente. Solo per valutare la complessita' algoritmica, non la velocita' computazionale vera. Per costruire l'Heap occorre conoscere il valore di tutte le celle remote, mentre la tua struttura ausiliaria e' locale. Inizializzare qualcosa a True o a False sarebbe comunque immediato. Atlrimenti, se proprio come discorso non ti piace, prova a valutare se per te una Dictionary<Point,bool> inizialmente vuota sia sufficiente, Dove popolare la Dictionary ogni volta che trovi un Point da gettarci dentro. Se sceglierai cosi' fai attenzione agli operatori di eguaglianza. In particolare la GetHashCode, che e' la funzione che viene usata dalle Dictionary. che dovra' restituire un valore univoco per ciascun Point. __________________ Se pensi che il tuo codice sia troppo complesso da capire senza commenti, e' segno che molto probabilmente il tuo codice e' semplicemente mal scritto. E se pensi di avere bisogno di un nuovo commento, significa che ti manca almeno un test. Ultima modifica di gugoXX : 20-07-2008 alle 10:17.

20-07-2008, 18:04	#55
marco.r Senior Member Iscritto dal: Dec 2005 Città: Istanbul Messaggi: 1817	ops. forse la mia versione ha un bug concettuale... meglio se ora controllo __________________ One of the conclusions that we reached was that the "object" need not be a primitive notion in a programming language; one can build objects and their behaviour from little more than assignable value cells and good old lambda expressions. —Guy Steele

20-07-2008, 20:21	#57
71104 Bannato Iscritto dal: Feb 2005 Città: Roma Messaggi: 7029	l'ho ottimizzato ancora: Codice: 0 isn't present - 0 calls 100 isn't present - 251 calls 32538 isn't present - 200 calls 20984 isn't present - 352 calls 32767 isn't present - 0 calls 32539 is present - 200 calls 26 is present - 250 calls 11672 is present - 1 calls 9790 is present - 449 calls 14089 is present - 63 calls credo che meglio di così non si possa fare, il mio attuale algoritmo è di una semplicità disarmante la complessità è O(N + M) edit - e con queste ultime modifiche ho anche ridotto l'occupazione di memoria: ho tolto la matrice ausiliare, non serviva più. Ultima modifica di 71104 : 20-07-2008 alle 20:23.

Strumenti
Mostra una versione stampabile Invia questa pagina per email