interfaz - manejo de gridlayout en java

¿Por qué este código O(n ^ 2) se ejecuta más rápido que O(n)?

Question

Esta pregunta ya tiene una respuesta aquí:

• ¿Puede un algoritmo O (n) superar a O (n ^ 2) en términos de tiempo de cálculo? 6 respuestas

He escrito código para dos enfoques para descubrir el primer carácter único en una cadena en LeetCode.

Declaración del problema: dada una cadena, encuentre el primer carácter que no se repite en ella y devuelva su índice. Si no existe, devuelve -1.

Ejemplos de casos de prueba:

s = "leetcode" devuelve 0.

s = "código de amor", devuelve 2.

Enfoque 1 (O (n)) (corríjame si me equivoco):

class Solution {
public int firstUniqChar(String s) {
HashMap<Character,Integer> charHash = new HashMap<>();
int res = -1;
for (int i = 0; i < s.length(); i++) {
Integer count = charHash.get(s.charAt(i));
if (count == null){
charHash.put(s.charAt(i),1);
}
else {
charHash.put(s.charAt(i),count + 1);
}
}
for (int i = 0; i < s.length(); i++) {
if (charHash.get(s.charAt(i)) == 1) {
res = i;
break;
}
}
return res;
}
}

Enfoque 2 (O (n ^ 2)):

class Solution {
public int firstUniqChar(String s) {
char[] a = s.toCharArray();
int res = -1;
for(int i=0; i<a.length;i++){
if(s.indexOf(a[i])==s.lastIndexOf(a[i])) {
res = i;
break;
}
}
return res;
}
}

En el enfoque 2, creo que la complejidad debería ser O (n ^ 2), ya que indexOf se ejecuta en O (n * 1) aquí.

Pero cuando ejecuto ambas soluciones en LeetCode, obtengo 19 ms de tiempo de ejecución para el enfoque 2 y 92 ms para el enfoque 1. Estoy confundido; ¿Por qué sucede eso?

Supongo que LeetCode prueba valores de entrada pequeños y grandes para los casos mejores, peores y promedio.

Actualizar:

Soy consciente del hecho de que O (n ^ 2 algoritmos) puede funcionar mejor para ciertos n <n1. En esta pregunta quería entender por qué sucede esto en este caso. es decir, qué parte del Enfoque 1 lo hace más lento.

LeetCode enlace a la pregunta

Answer 1

Considerar:

• f ₁ (n) = n ²
• f ₂ (n) = n + 1000

Claramente, f ₁ es O (n ² ) y f ₂ es O (n). Para una entrada pequeña (por ejemplo, n = 5), tenemos f ₁ (n) = 25 pero f ₂ (n)> 1000.

El hecho de que una función (o complejidad de tiempo) sea O (n) y otra que sea O (n ² ) no significa que la primera sea más pequeña para todos los valores de n, solo que hay una n más allá de la cual este será el caso .

Answer 2

He portado las funciones a C ++ (17) para ver si la diferencia fue causada por la complejidad del algoritmo o Java.

#include <map>
#include <string_view>
int first_unique_char(char s[], int s_len) noexcept {
std::map<char, int> char_hash;
int res = -1;
for (int i = 0; i < s_len; i++) {
char c = s[i];
auto r = char_hash.find(c);
if (r == char_hash.end())
char_hash.insert(std::pair<char, int>(c,1));
else {
int new_val = r->second + 1;
char_hash.erase(c);
char_hash.insert(std::pair<char, int>(c, new_val));
}
}
for (int i = 0; i < s_len; i++)
if (char_hash.find(s[i])->second == 1) {
res = i;
break;
}
return res;
}
int first_unique_char2(char s[], int s_len) noexcept {
int res = -1;
std::string_view str = std::string_view(s, s_len);
for (int i = 0; i < s_len; i++) {
char c = s[i];
if (str.find_first_of(c) == str.find_last_of(c)) {
res = i;
break;
}
}
return res;
}

El resultado fue:

El segundo es ~ 30% más rápido para leetcode .

Más tarde, me di cuenta de que

 if (r == char_hash.end())
char_hash.insert(std::pair<char, int>(c,1));
else {
int new_val = r->second + 1;
char_hash.erase(c);
char_hash.insert(std::pair<char, int>(c, new_val));
}

podría ser optimizado para

 char_hash.try_emplace(c, 1);

Lo que también confirma que la complejidad no es lo único. Hay "longitud de entrada", que otras respuestas han cubierto y, por último, noté que

La implementación también hace una diferencia. Un código más largo oculta oportunidades de optimización.

Answer 3

Karol ya dio una buena explicación para su caso especial. Quiero agregar un comentario general sobre la gran notación O para la complejidad del tiempo.

En general, esta complejidad de tiempo no le dice mucho sobre el rendimiento real. Solo le da una idea de la cantidad de iteraciones que necesita un algoritmo en particular.

Permítame ponerlo así: si ejecuta una gran cantidad de iteraciones rápidas, esto puede ser más rápido que ejecutar muy pocas iteraciones extremadamente lentas.

Answer 4

O (n ² ) es solo la complejidad en el peor de los casos del segundo enfoque.

Para las cadenas tales como bbbbbb...bbbbbbbbbaaaaaaaaaaa...aaaaaaaaaaa donde hay x B y x a, cada iteración del bucle toma alrededor de x pasos para determinar el índice, por lo tanto el total de a cabo pasos es de aproximadamente 2x 2 . Para x aproximadamente 30000, tomaría aproximadamente 1 ~ 2 segundo (s), mientras que la otra solución funcionaría mucho mejor.

En Probar en línea, este punto de referencia calcula que el enfoque 2 es aproximadamente 50 veces más lento que el enfoque 1 para la cadena anterior. Para x más grande, la diferencia es aún mayor (el enfoque 1 toma alrededor de 0.01 segundos, el enfoque 2 toma unos segundos)

Sin embargo:

Para cadenas con cada carácter elegido independientemente, uniformemente de {a,b,c,...,z} ^[1] , la complejidad del tiempo esperado debe ser O (n).

Esto es cierto suponiendo que Java utiliza el algoritmo de búsqueda de cadena ingenua, que busca el carácter uno por uno hasta que se encuentra una coincidencia, y luego vuelve inmediatamente. La complejidad del tiempo de la búsqueda es el número de caracteres considerados.

Se puede probar fácilmente (la prueba es similar a esta publicación de Math.SE - Valor esperado del número de vueltas hasta la primera cabeza ) que la posición esperada de un personaje en particular en una cadena independiente uniforme sobre el alfabeto {a,b,c,...,z} es O (1). Por lo tanto, cada llamada indexOf y lastIndexOf ejecuta en el tiempo O (1) esperado, y todo el algoritmo toma el tiempo O (n) esperado.

^[1] : En el desafío original de leetcode , se dice que

Puede asumir que la cadena contiene solo letras minúsculas.

Sin embargo, eso no se menciona en la pregunta.

Answer 5

Para cadenas muy cortas, por ejemplo, un solo carácter, el costo de crear HashMap , cambiar su tamaño, buscar entradas mientras se encajonan y deshacen el char de char en Character podría eclipsar el costo de String.indexOf() , que probablemente JVM considere caluroso e incorporado. camino.

Otra razón podría ser el costo de acceso a la memoria RAM. Con objetos adicionales HashMap , Character y Integer involucrados en una búsqueda, puede ser necesario un acceso adicional hacia y desde la RAM. El acceso único es de ~ 100 ns y esto puede sumar.

Eche un vistazo a Bjarne Stroustrup: por qué debe evitar las listas enlazadas . Esta conferencia ilustra que el rendimiento no es lo mismo que la complejidad y el acceso a la memoria puede ser un asesino para un algoritmo.

Answer 6

Primero, el análisis de complejidad no te dice mucho. Solía decirle cómo se compararían los algoritmos, en teoría, a medida que el tamaño del problema crece a un gran número (hacia el infinito, si lo desea), y hasta cierto punto todavía lo hace.
Sin embargo, el análisis de complejidad hace suposiciones que eran solo verdaderas hace unos 30 o 40 años y no son en absoluto ciertas en la actualidad (como, por ejemplo, todas las operaciones son iguales, todos los accesos son iguales). Vivimos en un mundo en el que los factores constantes son enormes, y no todas las operaciones son iguales, ni siquiera remotamente. En la medida en que debe considerarse con mucho cuidado, en ningún caso puede asumir que "esto es O (N), por lo que será más rápido". Eso es una gran falacia.

Para los números pequeños, mirar a la "gran O" no tiene ningún sentido, pero incluso para los grandes, tenga en cuenta que el factor constante puede desempeñar un papel enorme y dominante. No, el factor constante no es cero y no es despreciable. Nunca asumas eso.
El algoritmo teóricamente increíble que, por ejemplo, encuentra algo en mil millones de elementos con solo 20 accesos, puede ser mucho más lento que un algoritmo "malo" que toma 200,000 accesos, si en el primer caso cada uno de los 20 accesos causa un error de página con una búsqueda de disco (cada una de las cuales vale unos cien millones de operaciones). La teoría y la práctica no siempre van de la mano aquí.

Segundo, a pesar de ser idiomático y, en general, parecer una buena idea (es O (1), ¿eh?), El uso de un mapa hash es malo en muchos casos. No en todos los casos, pero esto es así. Compara lo que hacen los dos fragmentos de código.

El O (N ² ) convierte una cadena moderadamente pequeña en una matriz de caracteres una vez (lo que básicamente cuesta cero) y luego accede repetidamente a esa matriz de manera lineal. Lo que es prácticamente lo más rápido que puede hacer una computadora, incluso en Java. Sí, Java es independiente de cualquier cosa como memoria o cachés, pero eso no puede cambiar el hecho de que estas cosas existen. El acceso local a cantidades pequeñas / moderadas de datos en una forma principalmente lineal es rápido .

El otro fragmento de código inserta caracteres en un hashmap, asignando una estructura de datos para cada carácter. Sí, las asignaciones dinámicas en Java no son tan caras, pero aún así, las asignaciones no son gratuitas, y los accesos a la memoria no son contiguos.
Entonces, se calcula una función hash. Esto es algo que a menudo se pasa por alto con los mapas hash. Para un solo personaje, esta es (con suerte) una operación barata, pero no está ni lejos de ser gratuita ^[1] . Luego, la estructura de datos se inserta de alguna manera en un contenedor (que técnicamente no es más que otro acceso de memoria no coherente). Ahora, hay una buena posibilidad de una colisión, en cuyo caso se debe hacer algo más (encadenar, volver a lavar, lo que sea).
Más tarde, se vuelven a leer los valores del mapa hash, lo que nuevamente implica llamar a la función hash, buscar el depósito, posiblemente atravesar una lista y hacer una comparación en cada nodo (esto es necesario debido a la posibilidad de colisiones).

Por lo tanto, cada operación involucra al menos dos indirectas, más algunos cálculos. En general, eso es muy costoso en comparación con solo iterar un pequeño conjunto un par de veces.

^[1] No es un problema aquí para las claves de un solo carácter, pero aún así, es un dato divertido: la gente suele hablar de mapas hash en términos de O (1) que ya no es cierto con, por ejemplo, el encadenamiento, pero luego se sorprenden de que en realidad la clave sea la clave. es O (N) con respecto a la longitud de la clave. Lo que bien puede ser notable.

Answer 7

La notación O grande es una medida teórica de la forma en que un algoritmo se escala en términos de consumo de memoria o tiempo de cálculo con N : el número de elementos o operaciones dominantes, y siempre como N->Infinity .

En la práctica, N en tu ejemplo es bastante pequeño. Mientras que agregar un elemento a una tabla hash generalmente se considera amortizado O (1), también puede resultar en una asignación de memoria (nuevamente, dependiendo del diseño de su tabla hash). Esto puede no ser O (1), y también puede resultar en que el proceso realice una llamada del sistema al núcleo para otra página.

Tomando la solución O(n^2) : la cadena en a se encontrará rápidamente en el caché y probablemente se ejecutará sin interrupciones. El costo de una asignación de memoria única probablemente será mayor que el par de bucles anidados.

En la práctica con arquitecturas de CPU modernas, donde las lecturas de caché de formularios son órdenes de magnitud más rápidas que las de la memoria principal, N será bastante grande antes de usar un algoritmo teóricamente óptimo que supere a una estructura de datos lineal y una búsqueda lineal. Los árboles binarios son particularmente malas noticias para la eficiencia del caché

[Editar] es Java: la tabla hash contiene referencias al objeto java.lang.Character caja. Cada adición individual resultará en una asignación de memoria