जाओ: स्लाइस से एकाधिक प्रविष्टियों को हटाने का सबसे तेज़/साफ तरीका क्या है?

Question

कैसे आप नीचे दिए गए कोड में deleteRecords समारोह लागू करना होगा:

Example: 

type Record struct { 
    id int 
    name string 
} 

type RecordList []*Record 

func deleteRecords(l *RecordList, ids []int) { 
    // Assume the RecordList can contain several 100 entries. 
    // and the number of the of the records to be removed is about 10. 
    // What is the fastest and cleanest ways to remove the records that match 
    // the id specified in the records list. 
} 

Answer 1

मैं अपने मशीन पर कुछ सूक्ष्म बेंच मार्किंग किया था, उत्तर यहाँ में दिए गए तरीकों में से सबसे बाहर की कोशिश कर रहा है और यह कोड जब आप आईडी सूची में करीब 40 तत्वों से ऊपर मिल गया है बाहर सबसे तेजी से आता है:

func deleteRecords(data []*Record, ids []int) []*Record { 
    w := 0 // write index 

loop: 
    for _, x := range data { 
     for _, id := range ids { 
      if id == x.id { 
       continue loop 
      } 
     } 
     data[w] = x 
     w++ 
    } 
    return data[:w] 
} 

आपने यह नहीं कहा कि सूची में रिकॉर्ड के क्रम को संरक्षित करना महत्वपूर्ण है या नहीं। यदि आप नहीं करते हैं तो यह कार्य उपर्युक्त से तेज है और अभी भी काफी साफ है।

func reorder(data []*Record, ids []int) []*Record { 
    n := len(data) 
    i := 0 
loop: 
    for i < n { 
     r := data[i] 
     for _, id := range ids { 
      if id == r.id { 
       data[i] = data[n-1] 
       n-- 
       continue loop 
      } 
     } 
     i++ 
    } 
    return data[0:n] 
} 

जैसे आईडी की संख्या बढ़ती है, तो रैखिक खोज की लागत भी होती है। लगभग 50 तत्वों पर, मानचित्र का उपयोग करने या आईडी को देखने के लिए बाइनरी खोज करने से अधिक कुशल हो जाता है, जब तक आप मानचित्र को पुनर्निर्माण (या सूची का सहारा लेना) से बच सकते हैं। कई सौ आईडी में, यह नक्शा या बाइनरी खोज का उपयोग करने के लिए और अधिक कुशल हो जाता है भले ही आपको इसे हर बार पुनर्निर्माण करना है।

func deletePreserve(data []*Record, ids []int) []*Record { 
    wdata := make([]*Record, len(data)) 
    w := 0 
loop: 
    for _, x := range data { 
     for _, id := range ids { 
      if id == x.id { 
       continue loop 
      } 
     } 
     wdata[w] = x 
     w++ 
    } 
    return wdata[0:w] 
} 

Answer 2

यहाँ एक विकल्प है, लेकिन मैं आशा करता हूं वहाँ क्लीनर/तेजी से अधिक कार्यात्मक देख इस प्रकार हैं:

func deleteRecords(l *RecordList, ids []int) *RecordList { 
    var newList RecordList 
    for _, rec := range l { 
     toRemove := false 
     for _, id := range ids { 
     if rec.id == id { 
      toRemove = true 
     } 
     if !toRemove { 
      newList = append(newList, rec) 
     } 
    } 
    return newList 
} 

Answer 3

उपयोग vector package's Delete method के रूप में एक गाइड, या सिर्फ एक टुकड़ा के बजाय एक वेक्टर का उपयोग करें।

Answer 4

यदि आपने वर्णन किया है, जहां लेन (ids) लगभग 10 और लेन (* एल) कई सैकड़ों में है, तो यह अपेक्षाकृत तेज़ होना चाहिए, क्योंकि यह स्थान पर अद्यतन करके स्मृति आवंटन को कम करता है।

package main 

import (
    "fmt" 
    "strconv" 
) 

type Record struct { 
    id int 
    name string 
} 

type RecordList []*Record 

func deleteRecords(l *RecordList, ids []int) { 
    rl := *l 
    for i := 0; i < len(rl); i++ { 
     rid := rl[i].id 
     for j := 0; j < len(ids); j++ { 
      if rid == ids[j] { 
       copy(rl[i:len(*l)-1], rl[i+1:]) 
       rl[len(rl)-1] = nil 
       rl = rl[:len(rl)-1] 
       break 
      } 
     } 
    } 
    *l = rl 
} 

func main() { 
    l := make(RecordList, 777) 
    for i := range l { 
     l[i] = &Record{int(i), "name #" + strconv.Itoa(i)} 
    } 
    ids := []int{0, 1, 2, 4, 8, len(l) - 1, len(l)} 
    fmt.Println(ids, len(l), cap(l), *l[0], *l[1], *l[len(l)-1]) 
    deleteRecords(&l, ids) 
    fmt.Println(ids, len(l), cap(l), *l[0], *l[1], *l[len(l)-1]) 
} 

आउटपुट:

[0 1 2 4 8 776 777] 777 777 {0 name #0} {1 name #1} {776 name #776} 
[0 1 2 4 8 776 777] 772 777 {1 name #1} {3 name #3} {775 name #775} 

Answer 5

के बजाय बार-बार खोज आईडी, आप एक नक्शा इस्तेमाल कर सकते हैं। यह कोड मानचित्र के पूर्ण आकार को पूर्ववत करता है, और फिर केवल सरणी तत्वों को स्थानांतरित करता है। कोई अन्य आवंटन नहीं हैं।

func filter(sl []int, fn func(int) bool) []int { 
    result := make([]int, 0, len(sl)) 
    last := 0 
    for i, v := range sl { 
     if fn(v) { 
      result = append(result, sl[last:i]...) 
      last = i + 1 
     } 
    } 
    return append(result, sl[last:]...) 
} 

यह मूल उत्परिवर्तित नहीं है, लेकिन अपेक्षाकृत कुशल होना चाहिए:

func deleteRecords(l *RecordList, ids []int) { 
    m := make(map[int]bool, len(ids)) 
    for _, id := range ids { 
     m[id] = true 
    } 
    s, x := *l, 0 
    for _, r := range s { 
     if !m[r.id] { 
      s[x] = r 
      x++ 
     } 
    } 
    *l = s[0:x] 
} 

Answer 6

एक निजी परियोजना के लिए, मैं कुछ इस तरह से किया था। यह शायद बेहतर बस करना है:

func filter(sl []int, fn func(int) bool) (result []int) { 
    for _, v := range sl { 
     if !fn(v) { 
     result = append(result, v) 
     } 
    } 
    return 
} 

सरल और क्लीनर।

func filter(sl []int, fn func(int) bool) []int { 
    outi := 0 
    res := sl 
    for _, v := range sl { 
     if !fn(v) { 
      res[outi] = v 
      outi++ 
     } 
    } 
    return res[0:outi] 
} 

आप इस अनुकूलन कर सकते हैं copy उपयोग करने के लिए तत्वों की सीमाओं को कॉपी करने की है, लेकिन वह दो बार कोड और शायद इसके लायक नहीं है: आप में जगह करना चाहते हैं, तो आप शायद कुछ की तरह चाहते हैं।

func deleteRecords(l []*Record, ids []int) []*Record { 
    outi := 0 
L: 
    for _, v := range l { 
     for _, id := range ids { 
      if v.id == id { 
       continue L 
      } 
     } 
     l[outi] = v 
     outi++ 
    } 
    return l[0:outi] 
} 

:

तो, यह विशिष्ट मामले में, मैं शायद की तरह कुछ करना चाहते हैं (ध्यान दें:। अपरीक्षित)

कोई आवंटन, कुछ भी नहीं फैंसी, और सूची के किसी न किसी आकार संभालने रिकॉर्ड्स और आपके द्वारा प्रस्तुत आईड्स की सूची, एक साधारण रैखिक खोज करने की संभावना है साथ ही प्रशंसक चीजें, लेकिन बिना किसी ओवरहेड के। मुझे एहसास है कि मेरा संस्करण टुकड़ा और एक नया टुकड़ा लौटाता है, लेकिन यह गो में गैर-मूर्खतापूर्ण नहीं है, और यह आवंटित ढेर के लिए कॉलसाइट पर टुकड़ा को मजबूर करने से बचाता है।

Answer 7

बड़ा पर्याप्त l और आईडी यह क्रमबद्ध करने वाले (अधिक प्रभावी हो जाएगा) दोनों सूचियों पहले और उसके बाद करना है:

आप टुकड़ा के मूल सामग्री को संरक्षित करना चाहते हैं, तो कुछ इस तरह अधिक उपयुक्त है दो नेस्टेड loops के बजाय उन पर एक लूप