algorithm - data - stack in c
¿Generalizar la pila find-min/find-max a estadísticas de orden arbitrarias? (8)
En esta pregunta anterior , el OP solicitó una estructura de datos similar a una pila que admite las siguientes operaciones en O (1) cada vez:
- Push, que agrega un nuevo elemento encima de la pila,
- Pop, que elimina el elemento superior de la pila,
- Find-Max, que devuelve (pero no elimina) el elemento más grande de la pila, y
- Find-Min, que devuelve (pero no elimina) el elemento más pequeño de la pila.
Hace unos minutos encontré esta pregunta relacionada que pedía una aclaración sobre una estructura de datos similar que, en lugar de permitir que se consulten los valores máximo y mínimo, permite consultar el elemento mediano de la pila. Estas dos estructuras de datos parecen ser un caso especial de una estructura de datos más general que admite las siguientes operaciones:
- Empujar, que empuja un elemento encima de la pila,
- Pop, que aparece en la parte superior de la pila, y
- Find-Kth, que para un k fijo determinado cuando se crea la estructura , devuelve el kth elemento más grande de la pila.
Es posible admitir todas estas operaciones almacenando una pila y un árbol de búsqueda binario equilibrado que contiene los elementos k superiores, lo que permitiría que todas estas operaciones se ejecuten en tiempo O (log k). Mi pregunta es la siguiente: ¿ es posible implementar la estructura de datos anterior más rápido que esto? Es decir, ¿podríamos obtener O (1) para las tres operaciones? ¿O quizás O (1) para push y pop y O (log k) para la búsqueda de estadísticas de orden?
¿Qué pasaría si emparejas la pila con un par de Fibonacci Heaps ? Eso podría dar O (1) Push and FindKth amortizado, y O (lgN) borrar.
La pila almacena pares [valor, heapPointer]. Los montones almacenan punteros de pila.
Crea un MaxHeap, un MinHeap.
On Push:
si MaxHeap tiene menos de K elementos, inserte la parte superior de la pila en MaxHeap;
de lo contrario, si el nuevo valor es menor que la parte superior de MaxHeap, primero inserte el resultado de DeleteMax en el MinHeap, luego inserte el nuevo elemento en MaxHeap;
de lo contrario insértelo en el MinHeap. O (1) (o O (lgK) si se necesita DeleteMax)
En FindKth, devuelve la parte superior de MaxHeap. O (1)
En Pop, también haga un Eliminar (nodo) del montón del elemento emergente.
Si estaba en el MinHeap, has terminado. O (lgN)
Si estaba en MaxHeap, también realice un DeleteMin desde MinHeap e inserte el resultado en MaxHeap. O (lgK) + O (lgN) + O (1)
Actualizar:
Me di cuenta de que lo escribí como K''th más pequeño, no K''th más grande. También olvidé un paso cuando un nuevo valor es menor que el K''th más pequeño actual. Y ese paso empuja el inserto en el peor de los casos a O (lg K). Esto todavía puede estar bien para una entrada distribuida uniformemente y una K pequeña, ya que solo afectará ese caso en las inserciones K / N.
* movió la Nueva Idea a una respuesta diferente - se hizo demasiado grande.
@tophat tiene razón: dado que esta estructura podría usarse para implementar una ordenación, no puede tener menos complejidad que un algoritmo de ordenación equivalente. Entonces, ¿cómo hacer una clasificación en menos de O (lg N)? Utilice la clase de radix.
Aquí hay una implementación que hace uso de un Binary Trie . Insertar elementos en un Trie binario es esencialmente la misma operación que realizar una ordenación de radix. El costo de insertar y eliminar s O (m), donde m es una constante: el número de bits en la clave. Encontrar la siguiente clave más grande o más pequeña también es O (m), que se logra al dar el siguiente paso en un recorrido en orden de la profundidad primero.
Así que la idea general es usar los valores que se insertan en la pila como claves en el trie. Los datos para almacenar son el recuento de ocurrencia de ese elemento en la pila. Para cada elemento enviado: si existe en el trie, incremente su conteo, sino almacénelo con un conteo de 1. Cuando saque un ítem, encuéntrelo, disminuya el conteo y elimínelo si el conteo es ahora 0. Ambos Las operaciones son O (m).
Para obtener O (1) FindKth, realice un seguimiento de 2 valores: El valor del elemento Kth y cuántas instancias de ese valor se encuentran en el primer elemento K. (por ejemplo, para K = 4 y una pila de [1,2,3,2,0,2], el valor de Kth es 2 y el "iCount" es 2). Luego, cuando presiona valores <the KthValue, simplemente reduzca el número de instancias, y si es 0, haga un FindPrev en el trie para obtener el siguiente valor más pequeño.
Cuando aparezca valores mayores que KthValue, incremente el conteo de instancias si existen más instancias de ese valor, de lo contrario, haga un FindNext para obtener el siguiente valor más grande.
(Las reglas son diferentes si hay menos de K elementos. En ese caso, simplemente puede rastrear el valor máximo insertado. Cuando hay K elementos, el máximo será el Kth.)
Aquí hay una implementación en C Se basa en un BinaryTrie (construido con el ejemplo en PineWiki como base) con esta interfaz:
BTrie* BTrieInsert(BTrie* t, Item key, int data);
BTrie* BTrieFind(BTrie* t, Item key);
BTrie* BTrieDelete(BTrie* t, Item key);
BTrie* BTrieNextKey(BTrie* t, Item key);
BTrie* BTriePrevKey(BTrie* t, Item key);
Aquí está la función Push.
void KSStackPush(KStack* ks, Item val)
{
BTrie* node;
//resize if needed
if (ks->ct == ks->sz) ks->stack = realloc(ks->stack,sizeof(Item)*(ks->sz*=2));
//push val
ks->stack[ks->ct++]=val;
//record count of value instances in trie
node = BTrieFind(ks->trie, val);
if (node) node->data++;
else ks->trie = BTrieInsert(ks->trie, val, 1);
//adjust kth if needed
ksCheckDecreaseKth(ks,val);
}
Aquí está el ayudante para rastrear el KthValue
//check if inserted val is in set of K
void ksCheckDecreaseKth(KStack* ks, Item val)
{
//if less than K items, track the max.
if (ks->ct <= ks->K) {
if (ks->ct==1) { ks->kthValue = val; ks->iCount = 1;} //1st item
else if (val == ks->kthValue) { ks->iCount++; }
else if (val > ks->kthValue) { ks->kthValue = val; ks->iCount = 1;}
}
//else if value is one of the K, decrement instance count
else if (val < ks->kthValue && (--ks->iCount<=0)) {
//if that was only instance in set,
//find the previous value, include all its instances
BTrie* node = BTriePrev(ks->trie, ks->kthValue);
ks->kthValue = node->key;
ks->iCount = node->data;
}
}
Aquí está la función Pop
Item KSStackPop(KStack* ks)
{
//pop val
Item val = ks->stack[--ks->ct];
//find in trie
BTrie* node = BTrieFind(ks->trie, val);
//decrement count, remove if no more instances
if (--node->data == 0)
ks->trie = BTrieDelete(ks->trie, val);
//adjust kth if needed
ksCheckIncreaseKth(ks,val);
return val;
}
Y el ayudante para aumentar el KthValue.
//check if removing val causes Kth to increase
void ksCheckIncreaseKth(KStack* ks, Item val)
{
//if less than K items, track max
if (ks->ct < ks->K)
{ //if removing the max,
if (val==ks->kthValue) {
//find the previous node, and set the instance count.
BTrie* node = BTriePrev(ks->trie, ks->kthValue);
ks->kthValue = node->key;
ks->iCount = node->data;
}
}
//if removed val was among the set of K,add a new item
else if (val <= ks->kthValue)
{
BTrie* node = BTrieFind(ks->trie, ks->kthValue);
//if more instances of kthValue exist, add 1 to set.
if (node && ks->iCount < node->data) ks->iCount++;
//else include 1 instance of next value
else {
BTrie* node = BTrieNext(ks->trie, ks->kthValue);
ks->kthValue = node->key;
ks->iCount = 1;
}
}
}
Entonces, este algoritmo es O (1) para las 3 operaciones. También puede admitir la operación Mediana: Comience con KthValue = el primer valor, y siempre que el tamaño de la pila cambie en 2, realice una operación IncreaseKth o DecreasesKth. El inconveniente es que la constante es grande. Es solo una victoria cuando m <lgK. Sin embargo, para teclas pequeñas y K grandes, esta puede ser una buena elección.
Creo que tophat estaba diciendo, implementa una estructura de datos puramente funcional que solo soporta O (log k) insert y O (1) find-kth (almacenado en caché por insert), y luego haga una pila de estas estructuras. Inserte las inserciones en la versión superior e inserta la actualización, aparece la versión superior y pop-find opera en la versión superior. Esto es O (log k) / O (1) / (1) pero espacio super-lineal.
EDITAR: Estaba trabajando en O (1) push / O (1) pop / O (log k) find-kth, y creo que no se puede hacer. El algoritmo de clasificación al que se refiere tophat se puede adaptar para obtener √k estadísticas de orden espaciadas uniformemente de una matriz de longitud-k en el tiempo O (k + (√k) log k). El problema es que el algoritmo debe saber cómo se compara cada estadística de orden con todos los demás elementos (de lo contrario, podría ser incorrecto), lo que significa que ha agrupado todo en uno de √k + 1 cubos, lo que requiere Ω (k log (√k + 1)) = Ω (k log k) comparaciones sobre bases teóricas de la información. Ups.
Reemplazando √k por k eps para cualquier eps> 0, con O (1) push / O (1) pop, no creo que find-kth pueda ser O (k 1 - eps ), incluso con aleatorización y amortización.
Dado que la estructura se puede usar para ordenar los elementos k con O (k) operaciones push y find-kth, cada implementación basada en comparación tiene al menos uno de estos costos Omega (log k), incluso en un sentido amortizado, con aleatorización.
Push puede ser O (log k) y pop / find-kth puede ser O (1) (use estructuras de datos persistentes; push debe precalcular la estadística de orden). Mi intuición basada en trabajar con límites inferiores para algoritmos basados en comparación es que O (1) push / pop y O (log k) find-kth es factible pero requiere amortización.
La única implementación real en la que puedo envolver mi cabeza es Push / Pop O (log k) y Kth O (1).
- Apilar (enlace único)
- Montón mínimo (tamaño k)
- Stack2 (doblemente enlazado)
- Los nodos de valor se compartirán entre Stack, Heap y Stack2
EMPUJAR:
- Empujar a la pila
- Si valor> = raíz del montón
- Si el tamaño de pila <k
- Insertar valor en el montón
- Más
- Eliminar raíz del montón
- Empuje la raíz de pila eliminada a stack2
- Insertar valor en el montón
POPULAR:
- Pop de la pila
- Si el nodo reventado tiene referencias stack2
- Eliminar de la pila2 (eliminar la lista doblemente vinculada)
- Si el nodo emergente tiene referencias de pila
- Eliminar de la pila (intercambiar con el último elemento, realizar la pila arriba-abajo)
- Pop de stack2
- Si el elemento extraído de stack2 no es nulo
- Insertar elemento extraído de stack2 en el montón
KTH:
- Si el montón es tamaño k
- Devolver valor de raíz de montón
Podrías usar una lista de saltos . (Primero pensé en la lista enlazada, pero la inserción es O (n) y amit me corrigió con la lista de omisión. Creo que esta estructura de datos podría ser bastante interesante en su caso)
With this data structure, inserting/deleting would take O(ln(k))
and finding the maximum O(1)
Yo usaría :
- una pila, que contiene tus elementos
- aa pila que contiene el historial de la lista de saltos (que contiene los k elementos más pequeños)
(Me di cuenta de que era el elemento Kth más grande ... pero es más o menos el mismo problema)
al empujar (O (ln (k)):
si el elemento es menos el elemento kth, elimine el elemento kth (O (ln (k)) póngalo en la pila LIFO (O (1)) luego inserte el elemento en la lista de omisión O (ln (k))
de lo contrario, no está en la lista de omisión, simplemente póngalo en la pila (O (1))
Al empujar, agrega una nueva lista de omisión al historial, ya que esto es similar a una copia en escritura, no tomaría más que O (ln (k))
al hacer estallar (O (1):
acabas de saltar de las dos pilas
obteniendo k elemento O (1):
Siempre tome el elemento máximo en la lista (O (1))
Todos los ln (k) son costes amortizados.
Ejemplo:
Tomaré el mismo ejemplo que el tuyo (en Stack con find-min / find-max más eficiente que O (n)):
Supongamos que tenemos una pila y sumamos los valores 2, 7, 1, 8, 3 y 9, en ese orden. y k = 3
Lo representaré de esta manera:
[number in the stack] [ skip list linked with that number]
primero presiono 2,7 y 1 (no tiene sentido buscar el elemento kth en una lista de menos de k elementos)
1 [7,2,1]
7 [7,2,null]
2 [2,null,null]
Si quiero el elemento kth solo necesito tomar el máximo en la lista enlazada: 7
ahora empujo 8,3, 9
en la parte superior de la pila tengo:
8 [7,2,1] since 8 > kth element therefore skip list doesn''t change
entonces :
3 [3,2,1] since 3 < kth element, the kth element has changed. I first delete 7 who was the previous kth element (O(ln(k))) then insert 3 O(ln(k)) => total O(ln(k))
entonces :
9 [3,2,1] since 9 > kth element
Aquí está la pila que recibo:
9 [3,2,1]
3 [3,2,1]
8 [7,2,1]
1 [7,2,1]
7 [7,2,null]
2 [2,null,null]
encontrar k th elemento:
I get 3 in O(1)
Ahora puedo hacer saltar 9 y 3 (toma O (1)):
8 [7,2,1]
1 [7,2,1]
7 [7,2,null]
2 [2,null,null]
encontrar k elemento k:
I get 7 in O(1)
y presione 0 (toma O (ln (k) - inserción)
0 [2,1,0]
8 [7,2,1]
1 [7,2,1]
7 [7,2,null]
2 [2,null,null]
Si esto es realmente más rápido que su implementación de log k, dependiendo de qué operaciones se usan con más frecuencia, propongo una implementación con O (1) Find-kth y Pop y O (n) Push, donde n es el tamaño de pila. Y también quiero compartir esto con SO porque a primera vista es solo una estructura de datos divertidísima, pero incluso podría ser razonable.
Se describe mejor mediante una pila doblemente enlazada, o quizás más fácilmente descrita como un híbrido de una pila enlazada y una lista ordenada doblemente enlazada. Básicamente, cada nodo mantiene 4 referencias a otros nodos, el siguiente y el anterior en orden de pila y el siguiente y el anterior en orden ordenado en el tamaño del elemento. Estas dos listas vinculadas se pueden implementar utilizando los mismos nodos, pero funcionan completamente por separado, es decir, la lista enlazada ordenada no tiene que conocer el orden de la pila y viceversa.
Al igual que una pila enlazada normal, la colección en sí misma deberá mantener una referencia al nodo superior (y al final?). Para acomodar la naturaleza O (1) del método Find-kth, la colección también mantendrá una referencia al elemento kth más grande.
El método emergente funciona de la siguiente manera: el nodo emergente se elimina de la lista ordenada doblemente enlazada, al igual que una eliminación de una lista enlazada ordenada normal. Toma O (1) ya que la colección tiene una referencia a la parte superior. Dependiendo de si el elemento emergente era más grande o más pequeño que el elemento kth, la referencia al elemento kth más grande se establece en el anterior o el siguiente. Así que el método todavía tiene complejidad O (1).
El método de inserción funciona como una adición normal a una lista vinculada ordenada, que es una operación O (n). Comienza con el elemento más pequeño e inserta el nuevo nodo cuando se encuentra un elemento más grande. Para mantener la referencia correcta al elemento kth más grande, nuevamente se selecciona el elemento anterior o siguiente al elemento kth más grande actual, dependiendo de si el nodo empujado fue más grande o más pequeño que el elemento kth más grande.
Por supuesto, junto a esto, la referencia a la "parte superior" de la pila debe establecerse en ambos métodos. También está el problema de k> n, para el cual no ha especificado qué debe hacer la estructura de datos. Espero que quede claro cómo funciona, de lo contrario podría agregar un ejemplo.
Pero bueno, no es del todo la complejidad que esperabas, pero me parece una "solución" interesante.
Edición: Una implementación de la estructura descrita.
Se emitió una recompensa por esta pregunta, lo que indica que mi respuesta original no fue lo suficientemente buena: P ¿Quizás al OP le gustaría ver una implementación?
He implementado tanto el problema de la mediana como el problema de k fijo, en C #. La implementación del rastreador de la mediana es solo una envoltura alrededor del rastreador del elemento kth, donde k puede mutar.
Para recapitular las complejidades:
- Empuje toma O (n)
- El pop toma O (1)
- FindKth toma O (1)
- Cambio k toma O (delta k)
Ya he descrito el algoritmo en detalle razonable en mi publicación original. La implementación es entonces bastante sencilla (pero no es tan trivial para acertar, ya que hay muchos signos de desigualdad y si hay que tener en cuenta las declaraciones). He comentado solo para indicar lo que se ha hecho, pero no los detalles de cómo, ya que de lo contrario sería demasiado grande. El código ya es bastante largo para una publicación SO.
Quiero proporcionar los contratos de todos los miembros públicos no triviales:
-
Kes el índice del elemento en la lista enlazada ordenada para mantener una referencia también. Es mutable y cuando se establece, la estructura se corrige de inmediato para eso. -
KthValuees el valor en ese índice, a menos que la estructura aún no tenga k elementos, en cuyo caso devuelve un valor predeterminado. -
HasKthValueexiste para distinguir fácilmente estos valores predeterminados de los elementos que resultaron ser el valor predeterminado de su tipo. -
Constructors: un enumerable nulo se interpreta como un enumerable vacío, y un comparador nulo se interpreta como el valor predeterminado. Este comparador define el orden utilizado al determinar el valor kth.
Así que este es el código:
public sealed class KthTrackingStack<T>
{
private readonly Stack<Node> stack;
private readonly IComparer<T> comparer;
private int k;
private Node smallestNode;
private Node kthNode;
public int K
{
get { return this.k; }
set
{
if (value < 0) throw new ArgumentOutOfRangeException();
for (; k < value; k++)
{
if (kthNode.NextInOrder == null)
return;
kthNode = kthNode.NextInOrder;
}
for (; k >= value; k--)
{
if (kthNode.PreviousInOrder == null)
return;
kthNode = kthNode.PreviousInOrder;
}
}
}
public T KthValue
{
get { return HasKthValue ? kthNode.Value : default(T); }
}
public bool HasKthValue
{
get { return k < Count; }
}
public int Count
{
get { return this.stack.Count; }
}
public KthTrackingStack(int k, IEnumerable<T> initialElements = null, IComparer<T> comparer = null)
{
if (k < 0) throw new ArgumentOutOfRangeException("k");
this.k = k;
this.comparer = comparer ?? Comparer<T>.Default;
this.stack = new Stack<Node>();
if (initialElements != null)
foreach (T initialElement in initialElements)
this.Push(initialElement);
}
public void Push(T value)
{
//just a like a normal sorted linked list should the node before the inserted node be found.
Node nodeBeforeNewNode;
if (smallestNode == null || comparer.Compare(value, smallestNode.Value) < 0)
nodeBeforeNewNode = null;
else
{
nodeBeforeNewNode = smallestNode;//untested optimization: nodeBeforeNewNode = comparer.Compare(value, kthNode.Value) < 0 ? smallestNode : kthNode;
while (nodeBeforeNewNode.NextInOrder != null && comparerCompare(value, nodeBeforeNewNode.NextInOrder.Value) > 0)
nodeBeforeNewNode = nodeBeforeNewNode.NextInOrder;
}
//the following code includes the new node in the ordered linked list
Node newNode = new Node
{
Value = value,
PreviousInOrder = nodeBeforeNewNode,
NextInOrder = nodeBeforeNewNode == null ? smallestNode : nodeBeforeNewNode.NextInOrder
};
if (newNode.NextInOrder != null)
newNode.NextInOrder.PreviousInOrder = newNode;
if (newNode.PreviousInOrder != null)
newNode.PreviousInOrder.NextInOrder = newNode;
else
smallestNode = newNode;
//the following code deals with changes to the kth node due the adding the new node
if (kthNode != null && comparer.Compare(value, kthNode.Value) < 0)
{
if (HasKthValue)
kthNode = kthNode.PreviousInOrder;
}
else if (!HasKthValue)
{
kthNode = newNode;
}
stack.Push(newNode);
}
public T Pop()
{
Node result = stack.Pop();
//the following code deals with changes to the kth node
if (HasKthValue)
{
if (comparer.Compare(result.Value, kthNode.Value) <= 0)
kthNode = kthNode.NextInOrder;
}
else if(kthNode.PreviousInOrder != null || Count == 0)
{
kthNode = kthNode.PreviousInOrder;
}
//the following code maintains the order in the linked list
if (result.NextInOrder != null)
result.NextInOrder.PreviousInOrder = result.PreviousInOrder;
if (result.PreviousInOrder != null)
result.PreviousInOrder.NextInOrder = result.NextInOrder;
else
smallestNode = result.NextInOrder;
return result.Value;
}
public T Peek()
{
return this.stack.Peek().Value;
}
private sealed class Node
{
public T Value { get; set; }
public Node NextInOrder { get; internal set; }
public Node PreviousInOrder { get; internal set; }
}
}
public class MedianTrackingStack<T>
{
private readonly KthTrackingStack<T> stack;
public void Push(T value)
{
stack.Push(value);
stack.K = stack.Count / 2;
}
public T Pop()
{
T result = stack.Pop();
stack.K = stack.Count / 2;
return result;
}
public T Median
{
get { return stack.KthValue; }
}
public MedianTrackingStack(IEnumerable<T> initialElements = null, IComparer<T> comparer = null)
{
stack = new KthTrackingStack<T>(initialElements == null ? 0 : initialElements.Count()/2, initialElements, comparer);
}
}
Por supuesto, siempre es libre de hacer cualquier pregunta sobre este código, ya que me doy cuenta de que algunas cosas pueden no ser obvias por la descripción y los comentarios esporádicos
Utilice un Trie para almacenar sus valores. Los intentos ya tienen una complejidad de inserción O (1). Solo necesitas preocuparte por dos cosas, hacer estallar y buscar, pero si modificas un poco tu programa, sería fácil.
Al insertar (empujar), tenga un contador para cada ruta que almacena el número de elementos insertados allí. Esto permitirá a cada nodo realizar un seguimiento de cuántos elementos se han insertado usando esa ruta, es decir, el número representa la cantidad de elementos que se almacenan debajo de esa ruta. De esa manera, cuando intentes buscar el elemento kth, sería una comparación simple en cada ruta.
Para hacer estallar, puede tener un objeto estático que tenga un enlace al último objeto almacenado. Se puede acceder a ese objeto desde el objeto raíz, por lo tanto, O (1). Por supuesto, necesitaría agregar funciones para recuperar el último objeto insertado, lo que significa que el nuevo nodo empujado debe tener un puntero al elemento previamente empujado (implementado en el procedimiento de empuje; muy simple, también O (1)). También debe disminuir el contador, lo que significa que cada nodo debe tener un puntero al nodo principal (también simple).
Para encontrar el elemento kth (esto es para el elemento kth más pequeño, pero encontrar el más grande es muy similar): cuando ingresas cada nodo, pasas k y el índice mínimo para la rama (para la raíz sería 0). Luego haga una comparación simple para cada ruta: si (k entre el índice mínimo y el índice mínimo + contador de ruta), ingrese esa ruta pasando k y el nuevo índice mínimo como (índice mínimo + suma de todos los pathCounters anteriores, excluyendo el tomaste). Creo que esto es O (1), ya que aumentar los datos numéricos dentro de un cierto rango no aumenta la dificultad de encontrar k.
Espero que esto ayude, y si algo no está muy claro, házmelo saber.