Döngüleri içeren milyonlarca düğüm içeren bağlantılı bir listedeki döngüyü bul

Question

Bir röportaj sırasında bana soruldu. Bu sorunu çözmek için çeşitli yaklaşımları biliyorum. Ancak, milyonlarca düğüm noktasını içerdiği vurgulandı.

İki işaretçi yaklaşımı kullanarak bunu çözebileceğimizi biliyorum. Ayrıca HashMap kullanarak bunu çözebiliriz. Listenin milyonlarca düğümüne sahip olmasıyla optimize edilmiş çözümü bilmek istedi. Bundan sonra, listeyi birden fazla parçaya ayırmayı ve sonra işlemi sabitlemek için çoklu iş parçacığı uygulamanızı da önerdim. Ama tam memnun değildi. Odaklanmadığım başka bir yol var mı? Mulitthreading kullanarak, listeyi parçalara bölerken, ziyaret edilen bir sonraki düğümler kümesini de korumak zorundayız, döngü iki parçaya bölünmüş olabilir.

Hiçbir uygulama istemiyorum. Sadece bana biraz yön ver, böylece daha fazla düşünebilirim.

Answer 1

Eğer Floyd'un algoritmasıyla (iki işaretli şey) başladıysanız ve görüşmeci daha hızlı bir şey önermenizi istediyse, yanlış yöne gittiniz. Bir HashMap'in bakımı daha uzunyolunu alacaktır. Multithreading da yararlı değildir, çünkü bağlantılı bir liste ve işi bölmek için onu yürümek zorundasınız.

Brent algoritması ile başlayıp Floyd'un algoritmasından daha az sayıda işaretçiyi izleyen algoritmaya başlamıştım ve çoğu zaman daha hızlıdır çünkü önbellek dostu. Vikipedi, Brent'in algoritmasının iyi bir açıklamasına sahiptir: https://en.wikipedia.org/wiki/Cycle_detection#Brent.27s_algorithm

Ayrıca Brent'in algoritmasını çeşitli yollarla hızlandırmak da mümkündür. Brent'in algoritması, döngüyü bulmak için gerçekten ihtiyacınız olan iki kattan fazla düğümleri ziyaret etmenizi sağlar. Örneğin, 1 0'dan daha önceki bir düğümün kaydedilmesiyle basit tek yönlü birleştirici karma (çarpışmadan kaçınma yok), örneğin, bu faktörü isteğe bağlı olarak 1'e yakın olana kadar azaltabilirsiniz.