algorithm - ¿Estructura de datos para elegir elementos aleatorios?

language-agnostic data-structures

Question

¿Alguien sabe de una estructura de datos que soporte las dos operaciones de manera eficiente?

1. Insertar un valor en la estructura de datos.
2. Encolar y devolver una entrada de la estructura de datos con una probabilidad aleatoria uniforme.

Esto es algo así como la "bolsa de canicas" canónica que siempre aparece en las clases de probabilidad introductoria. Puede poner canicas arbitrarias en la bolsa, y luego removerlas de manera eficiente al azar.

La mejor solución que tengo es la siguiente: usar un árbol de búsqueda binaria de equilibrio automático (AVL, AA, rojo / negro, etc.) para almacenar los elementos. Esto da O (lg n) tiempo de inserción. Para eliminar un elemento aleatorio, seleccione un índice aleatorio i, luego localice y elimine el elemento i del árbol. Si ha aumentado la estructura de forma adecuada, también se puede hacer que se ejecute en tiempo O (lg n).

Este tiempo de ejecución ciertamente no es malo, pero tengo curiosidad por saber si es posible hacerlo mejor, ¿quizás O (1) para la inserción y O (lg n) para las salidas? ¿O tal vez algo que se ejecuta en el O (1) esperado insertar y eliminar usando funciones hash? ¿O tal vez un límite amortizado más fuerte?

¿Alguien tiene alguna idea sobre cómo hacer esto asintóticamente más rápido?

Answer 1

Sí. Usa un vector.

Para insertar, simplemente coloque al final e incremente el tamaño. Para eliminar, elija un elemento al azar, intercambie su contenido con el valor final, luego saque el valor final (es decir, devuelva el valor final y disminuya el tamaño del vector).

Ambas operaciones se amortizan en O (1).