Buscando algunos algoritmos clásicos en el campo de la programación que también sean algoritmos que los programadores deben dominar.
Vi esto en un foro, consúltalo. Funciones virtuales de C
======================
C utiliza funciones virtuales para implementar el estado de múltiples objetos, el Los primeros cuatro bytes del objeto C son punteros a la tabla de funciones virtuales. La secuencia de inicialización es primero la clase base y luego la clase derivada, por lo que la tabla de funciones virtuales siempre apunta a la última clase derivada, realizando así la misma función en diferentes objetos. Los diferentes comportamientos hacen que el objeto sea único e individual.
Algoritmo asociado para la asignación y el reciclaje del grupo de memoria
=========================
El algoritmo asociado es un algoritmo mejorado del método de lista enlazada libre. Establece sucesivamente una lista enlazada libre de bloques de memoria de tamaño 2^0\2^1\2^2\2^3...2^n. y utiliza socios de bloques de memoria adyacentes, es fácil fusionar bloques de memoria que son socios y moverlos a la lista vinculada libre correspondiente, o dividir una parte de la memoria en dos partes de la memoria asociada, asignar una parte y colgar. la otra pieza en la lista enlazada libre correspondiente, lo que facilita la asignación y el reciclaje de memoria.
árbol AVL
========================
el árbol AVL es un árbol binario equilibrado, en el que el orden transversal se ordena de pequeño a grande. Esta estructura es muy eficiente para insertar y recuperar nodos, y se usa ampliamente
Clasificación rápida
==. ======== ==============
A través de un paso de clasificación, los datos a ordenar se dividen en dos partes independientes. en una parte es más importante que todos los datos en la otra parte, y luego use este método para ordenar rápidamente las dos partes de los datos respectivamente. Todo el proceso de clasificación se puede realizar de forma recursiva, de modo que todos los datos se vuelvan ordenados. secuencia. Muy eficiente
Protocolo de cifrado asimétrico de criptografía (clave pública, protocolo de cifrado de clave privada)
==================== === ==
El algoritmo de cifrado asimétrico requiere dos claves. El texto cifrado generado por el cifrado con una de ellas solo puede ser descifrado por la otra clave. El poseedor de la clave A puede usar una de ellas. La clave pública se llama. clave pública, y la otra que se mantiene en secreto se llama clave privada. De esta manera, cuando alguien B quiere enviar una carta secreta a A, siempre que la carta secreta esté cifrada con la clave pública de A, puede utilizar varios métodos con confianza. El canal le pasó la superstición a A, porque solo A puede descifrar el mensaje secreto, y la interceptación por parte de un tercero no tiene sentido porque no se puede descifrar.
Este algoritmo resuelve muy bien el problema de la transmisión segura de claves, porque la clave pública y el algoritmo de cifrado son públicos y no es necesario transmitir la clave privada.
Protocolo de firma digital de criptografía (autenticación de identidad, anti-repudio)
=======================
Las firmas digitales también se basan en cifrado asimétrico. Si el Sr. A usa su clave privada para cifrar un archivo antes de publicarlo, el Sr. A no puede negar que el archivo fue liberado por él, porque otros pueden descifrar el archivo. a través de la clave pública de A significa que si el algoritmo es confiable, el archivo debe haber sido cifrado por A con su clave privada.
Debido a que el cifrado y descifrado de los algoritmos de cifrado asimétrico son muy lentos, la firma digital actual no cifra la información que se va a revelar con su clave privada, sino que primero utiliza un algoritmo hash único como (MD5) Generar. una huella digital relativamente corta (valor hash) de la información, cifra la huella digital con su clave privada y la publica junto con la información, lo que también logra el efecto anti-repudio.
Coincidencia de patrones de cadena sin algoritmo backtracking-kmp
=======================
Se basa en las características de la subcadena. Cuando la coincidencia falla, no es necesario retroceder. En cambio, la cadena se desliza directamente hacia atrás varios bytes y continúa coincidiendo, lo que mejora enormemente la velocidad de coincidencia. Este algoritmo es ampliamente utilizado. Consulte el tutorial de estructura de datos para obtener más detalles.
Selección de ruta mínima: algoritmo de Dijkstra, algoritmo de Freud
===================== ===
Al aprender estructuras de datos, los que más me impresionaron fueron el algoritmo kmp y el algoritmo de ruta mínima, porque se necesita mucha capacidad intelectual para entenderlos. Es imposible para mí inventar estos algoritmos. genio, jaja.
Una vez escribí una pequeña cosa para alguien que usaba el algoritmo del camino más corto y fue muy efectivo. Recuerdo que era una variante del algoritmo de Freud. Los amigos que quieran saber más sobre él pueden buscar información relevante. información Creo que úselos en su proyecto. Simplemente copie el código directamente del libro de texto, no es necesario comprenderlo.
algoritmo tcp protocolo-nagle
======================
tcp allí Hay muchas ideas sorprendentes en ip, y la más impresionante es el algoritmo nagle.
En aras de la eficiencia y el control del flujo, TCP no envía tantos datos como los que genera inmediatamente. Por lo general, espera hasta que los datos se acumulen hasta la mitad de la longitud del búfer de envío o los datos alcancen el TCP máximo. longitud de la parte de datos del paquete (parece ser 65515) antes de comenzar el envío, y también depende del tamaño del búfer disponible en el extremo receptor si el extremo receptor genera un mensaje de respuesta para notificar al extremo emisor que no hay. espacio para aceptar, el extremo emisor no comenzará incluso si el búfer está lleno hasta que el extremo receptor notifique al extremo emisor que tiene espacio para recibir datos.
Existe un problema si el remitente quiere enviar un mensaje pequeño (por ejemplo, 10 bytes) y luego esperar la respuesta de la otra parte. Según el esquema anterior, TCP esperará hasta que se recopile una cierta cantidad de datos antes de enviarlos, por lo que surge una contradicción. La capa de aplicación ya no envía datos. Si TCP no puede esperar suficientes datos, no enviará 10 palabras de datos a la tarjeta de red. Si la capa de aplicación del extremo receptor no puede recibir los datos, no responderá al extremo emisor.
También puede decir que puede modificar las condiciones de envío del remitente y que no tiene que esperar hasta que se envíen suficientes datos antes de enviar. Por razones de eficiencia, puede considerar retrasarlo durante un cierto período de tiempo. tiempo, como 1 segundo si la capa superior aún no llega datos, se enviarán los datos en el búfer de envío. Por supuesto, esto también es factible, aunque la aplicación esperó en vano durante 1 segundo y no hizo nada, jaja.
De hecho, el algoritmo nagle resuelve muy bien este problema. Lo que hace es que no es necesario esperar la primera transmisión después de que se establece el enlace. Los datos se ensamblan directamente en un mensaje TCP. enviado en el futuro, espere hasta que la cantidad de datos sea suficiente o espere el mensaje de confirmación del destinatario. El algoritmo es extremadamente simple y resuelve muy bien la contradicción anterior.
Diseño del modelo Socket io
========================
Bajo windows Hay dos modos de trabajo del socket:
1) Modo sincrónico
2) Modo asíncrono
El socket sincrónico tiene dos modos de trabajo:
1) Modo de bloqueo
2) Modo sin bloqueo
El modo de bloqueo es el modo de trabajo más simple. Tome el envío de datos TCP como ejemplo si no hay espacio en el envío. buffer, enviar La llamada no volverá. Esperará hasta que se puedan enviar algunos datos, incluso un byte. Sin embargo, el retorno de envío no significa que todos los datos que quiero enviar se hayan enviado a tcp, por lo que cuando envíe. devuelve, se debe verificar el número enviado esta vez, ajustar el puntero del búfer de envío y continuar enviando hasta que se envíen todos los datos al sistema.
Debido a sus características de bloqueo, bloqueará el hilo de envío, por lo que los programas de un solo hilo no son adecuados para usar la comunicación en modo de bloqueo. Generalmente, se utiliza un método para conectar un hilo, pero este método no. Adecuado para mantener múltiples programas conectados es una mala elección. Cuantos más subprocesos, mayor será la sobrecarga.
Los sockets en modo síncrono sin bloqueo no bloquearán el hilo de comunicación. Si el búfer de envío está lleno, la llamada de envío regresará inmediatamente. Si el búfer de recepción está vacío, recv no se bloqueará, por lo que la comunicación. El hilo debe llamar repetidamente a send o recv para intentar enviar o recibir datos, lo cual es un gran desperdicio de CPU.
En respuesta a la vergüenza del no bloqueo, los desarrolladores de interfaces inventaron tres modelos IO para resolver este problema:
1) Modelo de selección (select)
2 ) Modelo de selección asincrónica (AsyncSelect)
3) Modelo de selección de eventos (EventSeselect)
La idea es comprobar de antemano si se pueden leer, escribir, etc. basados en 1 o n sockets. en el tipo io.
En cuanto a la selección en sí, select está bloqueando y puede monitorear múltiples sockets al mismo tiempo. Siempre que uno de los sockets monitoreados pueda leerse y escribirse, la llamada secect regresará
El modelo de selección de eventos también delega el trabajo de monitorear el estado del socket al sistema, y el sistema notifica la aplicación de posibles operaciones de socket a través de eventos en el momento apropiado.
Además del modo de trabajo sincrónico, también existe el modo de trabajo asincrónico
El modo de trabajo asincrónico no se bloqueará porque la operación io en sí se delega al sistema y el sistema realiza la operación io Una vez completada, la aplicación se notifica a través de una rutina de devolución de llamada o un evento o paquete de finalización.
Hay dos modelos de IO y sus correspondientes métodos de trabajo asincrónicos. De hecho, estos dos modelos son la implementación de IO asincrónicos. por ventana:
1) Modelo superpuesto
2) Puerto de finalización
El modelo superpuesto notifica a la aplicación que el io se ha completado a través de un evento o rutina de devolución de llamada
Comparación completa del modelo de puerto. Complicado, el puerto de finalización en sí es en realidad una cola de paquetes de finalización de io.
La aplicación generalmente crea varios subprocesos para monitorear el puerto de finalización. Estos subprocesos intentan eliminar un paquete de finalización del puerto de finalización. Si hay uno, la eliminación se realiza correctamente y la aplicación procesa el paquete de finalización. De lo contrario, la aplicación monitorea que el subproceso del puerto de finalización esté bloqueado.
El modelo de selección se implementa a partir de la versión de sockets Berkeley Software Distribution (BSD) en UNIX. Los otros cuatro modelos io fueron inventados por Windows, y el puerto de finalización y el modelo de selección asíncrono se utilizan relativamente. , generalmente utilizado para el desarrollo del lado del servidor y del lado del cliente, respectivamente.
El diseño de estos cinco modelos IO es bastante inteligente: los tres modelos de selección resuelven bien las deficiencias de la programación en modo "síncrono sin bloqueo"; el modelo superpuesto y el puerto de finalización son las implementaciones clásicas de IO asíncrono de Windows; Limitado a IO de red, también se aplica a IO de archivos.
Para hacer una digresión, la finalización del envío del socket solo envía los datos (tal vez parte de ellos) al sistema, no que se hayan enviado a la tarjeta de red, ni que se hayan enviado al extremo receptor. Entonces, la única forma de saber que sus datos se han enviado a la capa de aplicación de la otra parte es pedirle a la otra parte que le envíe un paquete de respuesta.
Tenga cuidado al enviar datos. En correspondencia con TCP, es necesario evitar el desorden de envío y recepción. Para el envío, generalmente se debe establecer una cola de envío para cada enlace y se debe utilizar un algoritmo similar a nagle. utilizarse para iniciar el envío de datos.
Enviar una vez puede ser parte de los datos que envía. Tenga cuidado, de lo contrario no habrá forma de encontrar problemas.