比較鏈接列表和自定義鏈接列表的運行

Question

這是一項家庭作業，它並不難，這只是我的理解可能有缺陷。

所以我有兩個鏈表：一個雙向鏈表和一個自定義鏈表。我們只關心兩個函數：void add（）和布爾值包含（）。

MyLinkedList擴展AbstractList中和功能不變，但自定義LinkedList的延伸MyLinkedList和覆蓋了包括（）方法，當一個元素被擡起頭來，它總是會被移動到列表的前面，你知道，以提高更頻繁使用的單詞的查找時間。

它也覆蓋了add（）方法，使得項目不會添加到列表的後面，而是添加到列表的最前面。

而且我有一個dictionary.txt文件這是一個包含（〜10000字）的字典。

程序所做的是創建一個MyLinkedList對象和一個自定義鏈表對象，並將dictionary.txt單詞添加到相應的列表中。所以這應該意味着，在MyLinkedList中，單詞是按順序排列的，而在自定義鏈接列表中則是相​​反的順序。

然後該程序接受一個txt文件，例如romeo-and-juliet.txt並遍歷該txt文件的前10000個單詞，如果單詞匹配MyLinkedList對象中的單詞併爲自定義鏈表對象執行單獨運行。

問：爲什麼自定義鏈接列表運行得比MyLinkedList快？我的答案是，由於自定義鏈接列表將經常使用的搜索術語移到前面，所以查找時間更短，所以它的運行速度將比MyLinkedList快。我希望我的回答聽起來不錯，隨時可以改進。

現在一個令人費解的是，現在我們使用的是羅密歐和juliet.txt作爲字典文件本身，這是發生了什麼：

即最短的時間最長的一次：

1. MyLinkedList使用羅密歐和朱麗葉字典〜上dictionary.txt 80ms的

2. 自定義列表〜160毫秒

3. MyLinkedList上在羅密歐和朱麗葉字典〜dictionary.txt〜360ms

4. 自定義列表390ms

問：爲什麼會這樣？如果我們只使用故事中的詞語作爲詞典的範圍，那爲什麼它對自定義鏈表更慢？

P.S.如果問題的任何部分不清楚，請隨時告訴我，我會編輯我遺漏的任何內容。

Answer 1

自定義列表總是添加單詞前，詞典將在條款是如何在閱讀順序相反。對於普通字典，不會有太大的差別，但是當你使用羅密歐與朱麗葉本身作爲字典的文本，這就是你將要結束的：

Romeo and Juliet：「兩個家庭，兩個人都有尊嚴...比朱麗葉和她的羅密歐。」

MyLinkedList： 「兩個」， 「家庭」， 「既」， 「一點通」， 「中」， 「尊嚴」，...

custom list： 「羅密歐」， 「她」， 「和」 「朱麗葉」，「中」，「這個」，「比」，...

既然你是爲了尋找對R & j的文本，當你搜索對MyLinkedList的R &Ĵ字典，第一個字將始終在第一位置中找到，第二個字將始終被發現在第二位置上被發現等，作爲最壞的可能查找，或更快，如果字具有已經出現在劇中。

這很多，很多比在正常字典中查找每個單詞更快。

---

現在讓我們來看看當您開始搜索custom list時會發生什麼。你正在搜索的第一個單詞是字典中的最後一個單詞，或者如果它在劇本中出現多次，則是早期單詞。但是，與搜索MyLinkedList時相比，搜索時間肯定會更長。然後，更糟糕的是，您將該單詞移到字典的前面，將第二個單詞的「已知」位置推到字典的最後，然後再搜索它。這將有所減輕如常用詞（例如「一」，「該」，「和」）冒泡到前面，但它不會克服了大量的優點，即MyLinkedList搜索過。