8

Me preguntaba si alguien sabe que tipo de métodos son los de mayor rendimiento para implementarlos en búsquedas (en arrays) muy intensivas (hablo de arrays de millones de elementos) desde C#, por ejemplo es mejor utilizar IndexOf o BinarySearch para obtener el index del elemento? deberia usar arrays o HashSet? y como podria usar el HashSet para encontrar las coincidencias en el array?

Un ejemplo logico del algoritmo que necesito:

Bloque: 071827490593720123213023498230402000813

Valor a encontrar: 40200

Objetivo: Devolver el index donde se encuentra dicho grupo de numeros

Lo que debería devolver: 30

Código que implemento actualmente:

int offSet = 0;
while ((offSet = Array.IndexOf(bloque, encontrar[0], offSet)) != -1)
{
    if (encontrar.Length > 1)
        for (int i = 1; i < encontrar.Length; i++)
        {
            if (bloque.Length <= offSet + encontrar.Length) break;
            else if (encontrar[i] != bloque[offSet + i])
            {
                if (bloque[offSet + i] == encontrar[0])
                { offSet += (i - 1); break; }
                else if (i == encontrar.Length - 1)
                { offSet += i; break; }
                break;
            }
            else if (i == encontrar.Length - 1)
                addresses.Add(new IntPtr((int)baseAddress + offSet));
        }
    else addresses.Add(new IntPtr((int)baseAddress + offSet));
offSet++;
}

Este algoritmo no es lento, pero no es igual de rápido buscando que el programa con el que lo estoy comparando. El programa que estoy desarrollando abre los procesos y busca valores en sus regiones de memoria (Si, lo estoy comparando con Cheat Engine). Como pueden ver es mas o menos parecido al algoritmo de Boyer Moore, pero necesito saber si puedo reemplazar funciones para aumentar el rendimiento o si debería remover o cambiar algo en la lógica del algoritmo para aumentar el rendimiento.

https://es.wikipedia.org/wiki/Algoritmo_de_b%C3%BAsqueda_de_cadenas_Boyer-Moore

7
  • Diríamos que Cheat Engine implementa un algoritmo al menos un 30% mas rápido que este.
    – Mr.Noone
    el 1 sep. 2016 a las 1:58
  • 2
    No se si es aplicable a tu caso pero: ¿te has planteado dividir la cadena y hacer búsquedas de cada sub-parte de la cadena en diferentes hilos? el 1 sep. 2016 a las 10:24
  • 2
    Así de entrada. Utilizar Parallel.For :) el 1 sep. 2016 a las 15:33
  • Si me lo he planteado, de hecho es el siguiente paso, pero estoy buscando mejoras en la logica, primero quiero estar seguro que estoy implementando el mejor algoritmo para buscar direcciones de memoria
    – Mr.Noone
    el 2 sep. 2016 a las 0:11
  • Disculpa, me falto un detalle muy importante... Estoy corriendo en una laptop de arquitectura x86, por lo que la diferencia de rendimiento no se debe al paralelo si no al tipo de algoritmo.
    – Mr.Noone
    el 2 sep. 2016 a las 3:58

2 respuestas 2

2

Antes que nada, yo haría profiling de las ejecuciones para ver si me dicen algo del comportamiento del código.

Cosas que probaría, porque estas cosas entiendo son más prueba y error que otra cosa. Puede que en este tiempo hayas hecho:

  • Separar completamente el caso donde la longitud de encontrar es 1 (sacamos un if de loop.
  • Usar un for en vez de un while con lo que entiendo te podrías eliminar el offSet += (i - 1) quedándote sólo con el break
  • Buscaría delegar o retrasar la creación de objetos (es decir el addresses.Add(new IntPtr((int)baseAddress + offSet)). La instanciación y agregado a la colección podría ser costosa respecto a la ejecución del loop.

ACTUALIZACION

Racional: Estás haciendo un casteo, creando un objeto IntPtr y agregándolo a address. Puede que segunda operación en particular sea costosa en comparación con el resto del algoritmo, después de todo crear objetos no es gratis (es un hipótesis que deberías probar).

¿Qué se podría hacer al respecto? Bueno, podrías intentar delegar esa tarea a otro proceso o hilo.

Es decir, armar un esquema productor/consumidor, donde el productor (tu proceso actual) le pasa al consumidro la baseAddress+offset y el consumidor crea el IntPtr y lo agrega a su colección.

Luego al finalizar la ejecución, puedes pedirle al consumidor que crea el IntPtr que te devuelva la colección de IntPtr generada.

La idea es que en un ambiente multiprocesador el proceso de búsqueda y el de creación caigan en procesadorores distintos y con ello podrías ganar mejorar el rendimiento.

Acá un artículo al respecto.

FIN
Por supuesto, puedo estar equivocado en todo. Posiblemente sea mucho más interesante leer tus resultados en forma de respuesta.

2
  • Con que podría reemplazar la instanciacion y agregado a la colección? Es decir, si no hago eso no puedo coleccionar las direcciones, hay alguna otra forma de hacerlo?
    – Mr.Noone
    el 9 sep. 2016 a las 22:52
  • Podrías explicarme tu tercer punto? el primero lo acabo de hacer, no había sacado el if del loop (y aumento mucho el rendimiento), el segundo si, pero el tercero no lo entiendo, podría serme de gran ayuda.
    – Mr.Noone
    el 9 sep. 2016 a las 23:49
0

No evaluaste usar Regular Expression para buscar el bloque

con este podrias buscas todas las coincidencias

string bloque = "071827490593720123213023498230402000813";

Regex rx = new Regex("40200");
foreach (Match match in rx.Matches(bloque ))
{
   int i = match.Index;
}

Fuente: Is there a function that returns index where RegEx match starts?

2
  • Gracias Tuttini! pero solo puedo usar Regex con strings, puedo convertir un array of bytes de millones de caracteres en un segundo pero tenemos miles de regiones se harian miles de segundos de retraso, por lo que no es buena idea hacerlo :(
    – Mr.Noone
    el 2 sep. 2016 a las 18:40
  • Obviamente fue por mi error, mi fije que en ninguna parte he especificado que se trata de Arrays of Bytes y no strings
    – Mr.Noone
    el 2 sep. 2016 a las 19:42

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.