किसी सूची से सभी डुप्लिकेट कैसे निकालें?

Question

इस परीक्षण एप्लिकेशन पर विचार करें:

function RemoveDuplicates(const Input: IEnumerable<Integer>): IEnumerable<Integer>; 
begin 
    // How to implement this function? 
end; 

var 
    Enumerable: IEnumerable<Integer>; 
    UniqueEnumerable: IEnumerable<Integer>; 
begin 
    Enumerable := TCollections.CreateList<Integer>([1, 1, 2, 3, 3, 3, 4]); 
    UniqueEnumerable := RemoveDuplicates(Enumerable); 
    UniqueEnumerable.ForEach(
    procedure(const I: Integer) 
    begin 
     WriteLn(I); 
    end); 
    ReadLn; 
end. 

मैं RemoveDuplicates समारोह (इस हास्केल में nub कहा जाता है) कैसे लागू कर सकते हैं?

Answer 1

उपयोग क्या पहले से ही वहाँ है करता है:।

uses 
    Spring.Collections, 
    Spring.collections.Extensions; 

function RemoveDuplicates(const Input: IEnumerable<Integer>): IEnumerable<Integer>; 
begin 
    Result := TDistinctIterator<Integer>.Create(Input, nil); 
end; 

यह आलसी मूल्यांकन का समर्थन करता है (इसका मतलब है कि इनपुट नहीं मिल रहा है परिणामी गणना करने से पहले संसाधित हो रहा है)। यह पहले से ही मिली वस्तुओं (यह गणनाकर्ता के अंदर होता है) का ट्रैक रखने के लिए आंतरिक रूप से हैशसेट (वर्तमान में शब्दकोश के रूप में कार्यान्वित) का उपयोग कर रहा है।

यह महत्वपूर्ण क्यों है?चूंकि कोई भी ऑपरेशन जो पूर्ण गणना करता है, Input में अवांछित प्रदर्शन प्रभाव हो सकता है, जो अन्य महंगे संचालन शामिल करता है जो डुप्लीकेट को हटाने के अन्य दृष्टिकोणों (जैसे इसे सूची में डालने और उसे क्रमबद्ध करने) के अन्य दृष्टिकोणों के किसी भी लाभ से कहीं अधिक हो सकता है। इसके अलावा एक IENumerable सीमित होने की गारंटी नहीं है।

यदि इस फ़ंक्शन को कॉल करने और परिणाम की गणना करने के बीच Input बदल दिया गया था, तो परिवर्तन आपके गणना के नतीजे को प्रभावित कर रहा है, जबकि यदि आप आलसी मूल्यांकन का समर्थन नहीं कर रहे हैं तो ऐसा नहीं होगा। यदि आप कई बार गणना कर रहे हैं तो परिणाम हर बार भिन्न हो सकता है (यानी अद्यतित)।

Answer 2

एक मध्यवर्ती सूची का उपयोग करना:

function RemoveDuplicates(const Input: IEnumerable<Integer>): IEnumerable<Integer>; 
var 
    List: IList<Integer>; 
begin 
    List := TCollections.CreateList<Integer>; 
    Input.ForEach(
    procedure(const I: Integer) 
    begin 
     if not List.Contains(I) then 
     List.Add(I); 
    end); 
    Result := List; 
end; 

यह स्पष्ट रूप से सबसे अच्छा प्रदर्शन समाधान नहीं है, बेहतर विकल्प के लिए अन्य उत्तर देखें।

Answer 3

प्रदर्शन कारणों से मैं क्रमबद्ध सूची शब्दकोश का उपयोग करने का सुझाव देता हूं।

function RemoveDuplicates(const Input: IEnumerable<Integer>): IEnumerable<Integer>; 
var 
    Dictionary: IDictionary<integer, integer>; 
    Item: integer; 
begin 
    Dictionary := TCollections.CreateDictionary<integer,integer>; 
    for Item in Input do 
    Dictionary.AddOrSetValue(Item, 0);  

    Result := Dictionary.Keys; 
end; 

Answer 4

जेन्स के समाधान के लिए काम करेंगे, लेकिन यह हे की एक नहीं बल्कि धीमी गति से चल रहा है समय (एन) है।

एक बेहतर विकल्प है, तो आप एक लंबी सूची
है है - सूची
सॉर्ट - अपने उत्तराधिकारी के साथ हर आइटम की तुलना करें।

ओ (एन लॉग एन) के कुल चलने वाले समय की खोज के लिए Quicksort + O (n) के लिए ओ (एन लॉग एन) का चलने का समय है।

निम्नलिखित छद्म कोड (अब डेल्फी तक पहुंच नहीं है) देखें।

function RemoveDuplicates(const Input: IEnumerable<Integer>): IEnumerable<Integer>; 
var 
    List: IList<Integer>; 
    i: integer; 
begin 
    List := TCollections.CreateList<Integer>; 
    List.Assign(Input); //Copy input list to output. 
    List.Sort; 
    for i:= List.Count-1 downto 1 do begin 
    if List[i] = List[i-1] then List.delete(i); 
    //if Comparer<T>.Equals(List[i], List[i-1]) then .... 
    end; {for i} 
end; 

समस्याएं
इस दृष्टिकोण के साथ समस्या यह है कि निर्गम (हो सकता है) इनपुट से एक अलग आदेश है। यह एक समस्या हो सकती है या नहीं भी हो सकती है।

लाभ (या क्यों शब्दकोश बेकार)
छंटाई एक सस्ते ऑपरेशन है अगर यह सबसे तेजी से दृष्टिकोण होगा।
एक शब्दकोश का उपयोग हैशिंग के लिए उच्च निरंतर लागत रखता है।
हालांकि हैशिंग ऑपरेशन ओ (1) है, लेकिन यह बड़ी चाबियों के लिए बहुत महंगा हो सकता है, क्योंकि हैश हमेशा पूरी कुंजी को संसाधित करेगा, जबकि सॉर्टिंग तुलना जल्द ही एक अंतर का पता चल जाएगा। आगे ध्यान दें कि हैशिंग एक साधारण तुलना (लगभग 30x से 100x धीमी) की तुलना में अधिक महंगा संचालन है!

केवल जब सूची बहुत बड़ा है में Dictonary किक की बेहतर asymptotic प्रसारण समय