Hola vagabundos Nosotros, como viajeros en nuestros pensamientos y analizadores de nuestra condición, debemos entender dónde es bueno y dónde, exactamente dónde estamos, y quiero llamar la atención de los lectores sobre esto.
¿Cómo juntamos cadenas de pensamientos, secuencialmente, asumiendo la conclusión de cada paso, controlando el flujo de control y el estado de las células en la memoria? O simplemente describiendo el enunciado del problema, diciéndole al programa qué tarea particular desea resolver, y esto es suficiente para compilar todos los programas. No convierta la codificación en una secuencia de comandos que cambiarán el estado interno del sistema, sino que exprese el principio como el concepto de clasificación, porque no tiene que imaginar qué tipo de algoritmo está oculto allí, solo necesita obtener los datos ordenados. No es por nada que el presidente de Estados Unidos puede mencionar la Burbuja, expresa la idea de que entendió algo en programación. Acaba de descubrir que hay un algoritmo de clasificación, y los datos en la tabla de su escritorio, por sí mismos, no pueden alinearse, de alguna manera mágica, en orden alfabético.
Esta idea de que estoy bien dispuesto a la forma declarativa de expresar pensamientos, y de expresar todo con una secuencia de comandos y transiciones entre ellos, parece arcaica y anticuada, porque nuestros abuelos hicieron esto, los abuelos conectaron los contactos en el panel de conexiones y las luces parpadearon, y tenemos un monitor y reconocimiento de voz, ya que en este nivel de evolución aún puede pensar en seguir los comandos ... Me parece que si expresa el programa en un lenguaje lógico, se verá más comprensible, y esto se puede hacer. en tecnología, se hizo una apuesta en los años 80.
Bueno, la introducción se prolongó ...
Para empezar, intentaré volver a contar el mecanismo de clasificación rápida. Para ordenar una lista, debe dividirla en dos sublistas y combinar una sublista ordenada con otra sublista ordenada .
La operación de división debe poder convertir la lista en dos sublistas, una de ellas contiene todos los elementos menos básicos y la segunda lista solo contiene elementos grandes. Expresando esto, solo dos líneas están escritas en Erlang:
qsort([])->[]; qsort([H|T])->qsort([X||X<-T,X<H])++[H|qsort([X||X<-T,X>=H])].
Estas expresiones del resultado del proceso de pensamiento son de mi interés.
La clasificación imperativa es más difícil de describir. ¿Cómo podría haber una ventaja para este método de programación, y luego no lo llaman, a pesar de que hay un lugar-s, al menos un fortran? Es porque javascript, y todas las tendencias de las funciones lambda en los nuevos estándares de todos los idiomas, es una confirmación de los inconvenientes de la algorítmica.
Intentaré realizar un experimento para verificar las ventajas de un enfoque y otro, para probarlos. Trataré de mostrar que el registro declarativo de la definición de clasificación y su registro algorítmico se pueden comparar en términos de rendimiento y concluir cómo formular los programas más correctamente. Tal vez esto empuje la programación al estante a través de algoritmos y flujo de comandos, como enfoques simplemente obsoletos, que no son relevantes en absoluto, porque no está menos de moda expresarse en un Haskell o en una sección transversal. ¿Y tal vez no solo Fairy Sharp puede dar a los programas una apariencia clara y compacta?
Usaré Python para la demostración, ya que tiene varios paradigmas, y esto no es C ++ en absoluto y ya no es lisp. Puede escribir un programa claro en un paradigma diferente:
Ordenar 1
def qsort(S): if S==[]:return [] H,T=S[0],S[1:] return qsort([X for X in T if X<T])+[H]+qsort([X for X in T if X>=T])
Las palabras se pueden decir así: la ordenación toma el primer elemento como base, y luego todos los más pequeños se ordenan y se conectan a todos los más grandes, antes de eso .
O tal vez tal expresión funciona más rápido que la clasificación escrita en la forma torpe de una permutación de algunos elementos cercanos o no. ¿Es posible expresar esto más sucintamente y no requieren tantas palabras para esto? Trate de formular en voz alta el principio de clasificación por burbuja y dígaselo al Presidente de los Estados Unidos , porque obtuvo estos datos sagrados, aprendió sobre los algoritmos y lo puso, por ejemplo, así: Para ordenar la lista, debe tomar un par de elementos, compararlos entre sí y si el primero es más que el segundo, entonces deben intercambiarse, reorganizarse, y luego debe repetir la búsqueda de pares de tales elementos desde el comienzo de la lista hasta que terminen las permutaciones .
Sí, el principio de clasificar una burbuja incluso suena más largo que la versión de clasificación rápida, pero la segunda ventaja no es solo en la brevedad del registro, sino también en su velocidad, la expresión de la misma clasificación rápida formulada por el algoritmo será más rápida que la versión expresada expresamente? Tal vez necesitemos cambiar nuestros puntos de vista sobre la programación de la enseñanza, es necesario cómo los japoneses intentaron introducir la enseñanza del Prólogo y el pensamiento relacionado en las escuelas. Puede moverse sistemáticamente a la distancia de los lenguajes algorítmicos de expresión de pensamientos.
Ordenar 2
Para reproducir esto, tuve que recurrir a la literatura , esta es una declaración de Hoar , trato de convertirla en Python:
def quicksort(A, lo, hi): if lo < hi: p = partition(A, lo, hi) quicksort(A, lo, p - 1) quicksort(A, p + 1, hi) return A def partition(A, lo, hi): pivot = A[lo] i = lo - 1 j = hi + 1 while True do: i= i + 1 while A[i] < pivot do : j= j - 1 while A[j] > pivot if i >= j: return j A[i],A[j]=A[j],A[i]
Admiro el pensamiento, se necesita un ciclo interminable aquí, él habría insertado un go-that there)), hubo algunos bromistas.
Análisis
Ahora hagamos una larga lista y ordenemos por ambos métodos, y comprendamos cómo expresar nuestros pensamientos de manera más rápida y eficiente. ¿Qué enfoque es más fácil de tomar?
Creando una lista de números aleatorios como un problema separado, así es como se puede expresar:
def qsort(S): if S==[]:return [] H,T=S[0],S[1:] return qsort([X for X in T if X<H])+[H]+qsort([X for X in T if X>=H]) import random def test(len): list=[random.randint(-100, 100) for r in range(0,len)] from time import monotonic start = monotonic() slist=qsort(list) print('qsort='+str(monotonic() - start))
Aquí están las medidas obtenidas:
>>> test(10000) qsort=0.046999999998661224 >>> test(10000) qsort=0.0629999999946449 >>> test(10000) qsort=0.046999999998661224 >>> test(100000) qsort=4.0789999999979045 >>> test(100000) qsort=3.6560000000026776 >>> test(100000) qsort=3.7340000000040163 >>>
Ahora repito esto en la formulación del algoritmo:
def quicksort(A, lo, hi): if lo < hi: p = partition(A, lo, hi) quicksort(A, lo, p ) quicksort(A, p + 1, hi) return A def partition(A, lo, hi): pivot = A[lo] i = lo-1 j = hi+1 while True: while True: i=i+1 if(A[i]>=pivot) or (i>=hi): break while True: j=j-1 if(A[j]<=pivot) or (j<=lo): break if i >= j: return max(j,lo) A[i],A[j]=A[j],A[i] import random def test(len): list=[random.randint(-100, 100) for r in range(0,len)] from time import monotonic start = monotonic() slist=quicksort(list,0,len-1) print('quicksort='+str(monotonic() - start))
Tuve que trabajar para transformar el ejemplo original del algoritmo de fuentes antiguas a Wikipedia. Entonces, esto: debe tomar el elemento de soporte y organizar los elementos en la submatriz para que todo esté cada vez menos a la izquierda y más y más a la derecha. Para hacer esto, cambie la izquierda con el elemento derecho. Repetimos esto para cada sublista del elemento de referencia dividido por el índice, si no hay nada que cambiar, terminamos .
Total
Veamos cuál será la diferencia horaria para la misma lista, que se ordena por dos métodos. Realizaremos 100 experimentos y construiremos un gráfico:
import random def test(len): t1,t2=[],[] for n in range(1,100): list=[random.randint(-100, 100) for r in range(0,len)] list2=list[:] from time import monotonic start = monotonic() slist=qsort(list) t1+=[monotonic() - start]
Lo que se puede ver aquí: la función quicksort () funciona más rápido , pero su registro no es tan obvio, aunque la función es recursiva, pero no es nada fácil entender el trabajo de las permutaciones realizadas en ella.
Bueno, ¿qué expresión de pensamiento clasificador es más consciente?
Con una pequeña diferencia en el rendimiento, obtenemos una gran diferencia en el volumen y la complejidad del código.
Tal vez la verdad sea suficiente para aprender idiomas imperativos, pero ¿qué es más atractivo para usted?
PS. Y aquí está el Prólogo:
qsort([],[]). qsort([H|T],Res):- findall(X,(member(X,T),X<H),L1), findall(X,(member(X,T),X>=H),L2), qsort(L1,S1), qsort(L2,S2), append(S1,[H|S2],Res).