मैं सरणी में एकाधिक प्रविष्टियों को कुशलतापूर्वक कैसे संभाल सकता हूं?

Question

मेरे पास पूर्णांक की गतिशील आवंटित सरणी है जिसमें मैं मनमानी स्थितियों पर पूर्णांक डालना चाहता हूं। 2.5 मिलियन से अधिक में कई पूर्णांक।

मेरे कोड वर्तमान में इस तरह दिखता है:

type 
    TIntegerArr = array of Integer; 

var 
    FCount: Integer; 
    FSortedList: TIntegerArr; 

procedure Insert(_Value: Integer; _InsertPos: integer); 
var 
    OldList: TIntegerArr; 
begin 
    OldList := FSortedList; 
    if Length(FSortedList) < FCount + 1 then begin 
    OldList := FSortedList; 
    FSortedList := nil; 
    SetLength(FSortedList, FCount + 100); 
    CopyMemory(@FSortedList[0], @OldList[0], SizeOf(Integer) * _InsertPos); 
    end; 
    MoveMemory(@FSortedList[_InsertPos + 1], @OldList[_InsertPos], SizeOf(Integer) * (FCount - _InsertPos)); 
    FSortedList[_InsertPos] := _Value; 
    Inc(FCount); 
end; 

एक अस्थायी सूची का उपयोग करना और के बजाय ले जाएँ का उपयोग कर (वास्तविक कोड एक वर्ग है कि खेतों के रूप में FSortedList और FCount है की एक विधि है।) डेटा को स्थानांतरित करने के लिए लूप के लिए प्रदर्शन में काफी सुधार हुआ है क्योंकि यह बढ़ने के बाद सरणी को दो बार कॉपी करने से रोकता है (एक बार मौजूदा सरणी पर सेटलेथेंथ में और मूव के साथ एक और समय)।

लेकिन सबसे खराब केस सम्मिलित करें (कुछ वैल्यू, 0) अभी भी सभी मौजूदा मानों को हमेशा चलाता है।

अब तक मैं सरणी की शुरुआत में ऑफसेट शुरू करने की लाइनों के साथ सोच रहा था, इसलिए हर मौजूदा मूल्य को हर बार एक नया मूल्य डालने के बजाय, मौजूदा समय में स्थानांतरित करने की बजाय, मैं ऑफसेट कर सकता था तक पहुँच जाता है 0. उदाहरण के लिए:

// simple case: inserting at Position 0: 
if FOffset = 0 then begin 
    // [...] reallocate a new array as above 
    Move(@FSortedList[100], @OldList, SizeOf(Integer) * _InsertPos); 
    FOffset := 100; 
end; 
Dec(FOffset); 
FSortedList[FOffset] := _NewValue; 

निश्चित रूप से यह है कि क्या सम्मिलन बिंदु शुरुआत या अंत के नजदीक और कहा कि इस कदम के आधार पर या तो पहले है की जाँच करने के लिए बढ़ाया जा सकता है (यह कोड अपरीक्षित और शायद गाड़ी है) या अंतिम मान एक स्थिति से है ताकि औसत पर केवल 1/4 प्रविष्टियों को 1/2 के बजाय स्थानांतरित किया जाना चाहिए जैसा कि वर्तमान में है।

एक और विकल्प एक स्पैस सरणी लागू करेगा। मुझे 1 99 0 के दशक में कुछ वाणिज्यिक पुस्तकालय में इस तरह के कार्यान्वयन को याद रखना याद है, लेकिन याद नहीं है कि यह कौन सा था (टर्बोपावर?)।

यह प्रक्रिया कुछ सॉर्टिंग और इंडेक्सिंग कोड के लिए केंद्रीय है जो विभिन्न आकारों के सरणी पर काम करती है, उपर्युक्त लाखों प्रविष्टियों तक केवल कुछ दर्जन प्रविष्टियों से।

वर्तमान में प्रोग्राम लगभग 2 घंटे चलता है (मेरे अनुकूलन से पहले यह 5 घंटे के करीब था) और मुझे पहले से ही पता है कि सरणी में प्रविष्टियों की संख्या कम से कम दोगुनी हो रही है। जैसा कि सम्मिलन प्रदर्शन खराब हो जाता है, सरणी पहले से ही बड़ी है, मुझे संदेह है कि प्रविष्टियों की संख्या दोगुनी है, रन टाइम कम से कम चौगुनी होगी।

मुझे प्रदर्शन को ट्यून करने के बारे में कुछ सुझाव चाहिए। मेमोरी खपत वर्तमान में एक मुद्दा नहीं है लेकिन रन टाइम निश्चित रूप से है।

(यह डेल्फी 2007 लेकिन वह बहुत अधिक अंतर नहीं करना चाहिए जब तक कि नए डेल्फी संस्करण पहले से ही ऊपर करने के लिए एक अनुकूलित पुस्तकालय है Classes.TList अनुकूल नहीं है।।)

Edit1: बस विरल पाया सरणी कार्यान्वयन मैंने उपर्युक्त उल्लेख किया है: यह टर्बोपावर SysTools से StColl है।

संपादित 2: ठीक है, कुछ पृष्ठभूमि: मेरा प्रोग्राम वर्तमान में 2.4 मिलियन प्रविष्टियों के साथ एक डीबेस तालिका पढ़ता है और इन प्रविष्टियों से कई नई टेबल उत्पन्न करता है। नई टेबल सामान्यीकृत की जाती हैं और उन्हें बनाए जाने के बाद अनुक्रमित किया जाता है (प्रदर्शन कारणों से मैं डेटा डालने से पहले इंडेक्स उत्पन्न नहीं करता हूं, मेरा विश्वास करो, मैंने पहले इसे आजमाया।)। सरणी कोड का केंद्रीय टुकड़ा है जो जेनरेट टेबल के लिए आंतरिक सॉर्टिंग प्रदान करता है। नए रिकॉर्ड केवल तालिका में संलग्न होते हैं, लेकिन उनके रिकनो को क्रमबद्ध क्रम में सरणी में डाला जाता है।

Answer 1

नहीं बिगाड़ सकता है, लेकिन समाधान मेरे सवाल का संपादन में पहले से ही है:

TurboPower's StColl को एक सरणी प्रदर्शन नहीं रह गया है बड़े सरणियों के साथ खराब हो और काफी बूट करने के लिए तेजी से होता है से स्विच करने के बाद। रन टाइम 2 घंटे से 1/2 घंटे से कम है। परिवर्तन वास्तव में सरल था। काश मैं उस पुस्तकालय को बहुत पहले याद किया था।

मैं SourceForge भंडार (मैं पूरी पुस्तकालय डाउनलोड करने के लिए नहीं करना चाहता था) से निम्न फ़ाइलों की जरूरत:

• StBase.pas
• StColl.pas
• StConst.pas
• StList.pas
• StDefine.inc

असल में मैं कर रहा हूँ रों इस बात का अपमान किया कि अधिक परस्पर निर्भरता नहीं थी। टर्बोपावर लोग निश्चित रूप से अपने व्यापार को जानते थे। मुझे आश्चर्य है कि वे आज क्या कर रहे हैं, अभी भी कैसीनो के लिए जुआ मशीनों को प्रोग्रामिंग कर रहे हैं?

Answer 2

आपकी प्रक्रिया को देखने के तुरंत बाद मैंने कुछ त्रुटियों को देखा। प्रगति देखने के लिए मैंने सबसे पहले आपके मौजूदा प्रक्रिया की गति को सबसे खराब स्थिति परिदृश्य में मापा है (0 स्थिति पर सभी नंबर जोड़ना)।

n:=500000; 
for i:=0 to n-1 
do Insert(i, 0); 

मापन: एन = 500000 47.6 एमएस

ए) सादगी

मैं अपनी प्रक्रिया से कुछ अनावश्यक लाइनें नष्ट कर दिया (OldList पूरी तरह अनावश्यक है, SetLength स्मृति को बरकरार रखता है)।

सुधार एक:

procedure Insert(_Value: Integer; _InsertPos: integer); 
begin 
if Length(FSortedList) < FCount + 1 
    then SetLength(FSortedList, FCount + 100); 
    Move(FSortedList[_InsertPos], FSortedList[_InsertPos+1], SizeOf(Integer) * (FCount - _InsertPos)); 
    FSortedList[_InsertPos] := _Value; 
    Inc(FCount); 
end; 

गति हासिल 6% (44.8 एमएस)

बी) सब कुछ मायने रखता है

if Length(FSortedList) < FCount + 1 
    then SetLength(FSortedList, FCount + 100); 

• टिप 1: समारोह की लंबाई मैं हर डालने पर बुलाया रहा
• टिप 2: FCount + 1 हर बार गणना की जाती है
• युक्ति 3: स्थिरांक के रूप में (संदर्भ द्वारा) प्रक्रिया मापदंडों
• युक्ति 4: से बढ़ रही लंबाई: परिचय FCapacity चर
• युक्ति 5 केवल 100 बहुत सारे पुनर्वितरण (25,000 सरणी पर 25,000) का कारण बनेंगे। जैसा कि आप कहते हैं, स्मृति समस्या नहीं है, तो क्यों न केवल सभी या कम से कम बड़े आवंटित?

सुधार बी:

procedure Insert(const _Value, _InsertPos: integer); 
begin 
if FCount = FCapacity 
    then begin 
    Inc(FCapacity, 100000); 
    SetLength(FSortedList, FCapacity); 
    end; 
Move(FSortedList[_InsertPos], FSortedList[_InsertPos+1], SizeOf(Integer) * (FCount - _InsertPos)); 
FSortedList[_InsertPos] := _Value; 
Inc(FCount); 
end; 

गति हासिल 1% (44.3 एमएस)।

संकेत: 100000 तक इंक के बजाय आप कुछ प्रगतिशील एल्गोरिदम लागू कर सकते हैं।

सी) टोंटी

अगर हम अब प्रक्रिया को देखो, वहाँ कुछ भी नहीं छोड़ दिया है, सिर्फ स्मृति चाल का एक बहुत कुछ है। अगर हम एल्गोरिदम नहीं बदल सकते हैं, तो हमें स्मृति चाल में सुधार करना होगा।

वास्तव में fastmove चुनौती (fastcode.sourceforge.net)

मैं सिर्फ उन फ़ाइलों को तुम्हारी जरूरत है (3 फ़ाइलें, स्रोत कोड) के साथ एक ज़िप तैयार, नहीं था। लिंक >>>http://www.dakte.org/_stackoverflow/files/delphi-fastcode.zip

• अपनी परियोजना में fastcodeCPUID.pas और fastmove.pas जोड़ें!
• fastmove.pas का उपयोग करें;
• वोला! बदलने के लिए और कुछ नहीं! मेरी मशीन लगभग 50% पर

स्पीड लाभ (सीपीयू उपयोग कर रहे हैं पर निर्भर करता है)।

मूल प्रक्रिया

n   ms graph 
--------------------------------- 
100000 1.8 * 
200000 7.6 *** 
300000 17.0 ******* 
400000 30.1 ************* 
500000 47.6 ******************** 

सुधार, fastmove बिना (-7%)

n   ms graph 
--------------------------------- 
100000 1.6 * 
200000 6.9 *** 
300000 15.7 ****** 
400000 28.2 *********** 
500000 44.3 ****************** 

, बेहतर fastmove के साथ (-46%)

n   ms graph 
--------------------------------- 
100000 0.8 * 
200000 3.8 ** 
300000 9.0 **** 
400000 16.3 ******* 
500000 25.7 *********** 

अंतिम टिप्पणियां:

if FCount = FCapacity 
    then begin 
    if FCapacity<100000 
     then FCapacity:=100000 
     else FCapacity:=FCapacity*2; 
    SetLength(FSortedList, FCapacity); 
    end; 

जैसा कि मैंने आपको कुछ प्रगतिशील FCapacity वृद्धि जोड़ सकते हैं ने कहा। यह कुछ शास्त्रीय विकास कार्यान्वयन है (अगर आवश्यक हो तो अधिक जोड़ें या 100000 को अधिक अनुचित मूल्य में बदलें)।

डी) अद्यतन 2: सरणी^TArray

type 
    PIntegerArr3 = ^TIntegerArr3y; 
    TIntegerArr3y = array[0..1] of Integer; 

var 
FCapacity3, 
FCount3: Integer; 
FSortedList3: PIntegerArr3; 

procedure ResizeArr3(var aCurrentArr: PIntegerArr3; const aNewCapacity: Integer); 
var lNewArr: PIntegerArr3; 

begin 
GetMem(lNewArr, aNewCapacity*SizeOf(Integer)); 

if FCount3>0 // copy data too 
    then begin 
    if aNewCapacity<FCount3 
     then FCount3:=aNewCapacity; // shrink 
    Move(aCurrentArr^[0], lNewArr^[0], FCount3*SizeOf(Integer)); 
    end; 

FreeMem(aCurrentArr, FCapacity3*SizeOf(Integer)); 
FCapacity3:=aNewCapacity; 
aCurrentArr:=lNewArr; 
end; 

procedure FreeArr3; 
begin 
if FCapacity3>0 
    then begin 
    FreeMem(FSortedList3, FCapacity3*SizeOf(Integer)); 
    FSortedList3:=nil; 
    end; 
end; 

procedure Insert3(const _Value, _InsertPos: integer); 
begin 
if FCount3 = FCapacity3 
    then ResizeArr3(FSortedList3, FCapacity3 + 100000); 
Move(FSortedList3^[_InsertPos], FSortedList3^[_InsertPos+1], SizeOf(Integer) * (FCount3 - _InsertPos)); 
FSortedList3^[_InsertPos] := _Value; 
Inc(FCount3); 
end; 

स्पीड लाभ से कदम सी) कोई नहीं के रूप में!

परामर्श: फास्टमोव या एल्गोरिदम परिवर्तन, स्मृति चलती गति की "भौतिक" सीमा तक पहुंच गई है!

मैं डेल्फी XE3 और सिस्टम में उपयोग कर रहा हूं।क़दम, लाइन 5307:

(* ***** BEGIN LICENSE BLOCK ***** 
* 
* The assembly function Move is licensed under the CodeGear license terms. 
* 
* The initial developer of the original code is Fastcode 
* 
* Portions created by the initial developer are Copyright (C) 2002-2004 
* the initial developer. All Rights Reserved. 
* 
* Contributor(s): John O'Harrow 
* 
* ***** END LICENSE BLOCK ***** *) 

procedure Move(const Source; var Dest; Count: NativeInt); 

तो वास्तव में डेल्फी में allready कुछ Fastcode दिनचर्या हैं, लेकिन उनके साइट से सीधे डाउनलोड किए गए सहित (या लिंक से मैं ऊपर शामिल है) सबसे बड़ी diferrence बनाया है, लगभग 50% (अजीब)।