Soru Bir koleksiyonda yinelenen öğeleri bulmak ve gruplandırmak için hızlı algoritmalar nelerdir?


Öğelerin bir koleksiyonuna sahip olduğunuzu varsayalım, bunları çiftleri olanları seçip en az karşılaştırmalı olarak her bir gruba nasıl yerleştirebilirsiniz? tercihen C ++ 'da, fakat algoritma dilden daha önemlidir. Örneğin {E1, E2, E3, E4, E4, E2, E6, E4, E3} verildiğinde, {E2, E2}, {E3, E3}, {E4, E4, E4} çıkarımlarını yapmak istiyorum. Hangi veri yapısını ve algoritmayı seçeceksiniz? Ayrıca, std :: multimap gibi önceden sıralanmış bir tane varsa, veri yapısının kurulum maliyetini de belirtin.

Güncellemeler

Önerilenleri daha net yapmak için. bir kısıtlama var: öğeler kendileriyle karşılaştırılmalıdır Çoğal olduklarından emin olmak için.

Bu yüzden karmalar uygulanmaz, çünkü karşılaştırmayı ağır elementlerden (örneğin, veri parçaları) ışık elemanlarına (tamsayılar) kaydırırlar ve bazı karşılaştırmaları azaltırlar, ancak onlarla birlikte uzaklaşmazlar ve sonunda Orijinal problemimiz, bir çarpışma kovanının içinde olduğunda.

Her biri GB'lerin birer kopyasını çoğalttığını varsayalım, her bir hash-algoritması insanın bildiği aynı karma değerini taşıyorlar. Şimdi gerçek kopyaları göreceksiniz.

Hayır, bu gerçek bir yaşam problemi olamaz (MD5 bile gerçek hayat dosyaları için benzersiz bir karma oluşturmak için yeterlidir). Ama sadece yapabildiğimiz gibi yap. En az miktarda karşılaştırma içeren veri yapısını + algoritmasını bulmaya odaklanın.


Yaptığım şey

  1. bir STL std :: liste veri yapısına (bu 1'de) temsil eder, eleman silme işlemi, bir vektörden (2) daha ucuzdur, daha ucuzdur, sıralama gerektirmez.)

  2. bir öğe çıkar ve geri kalanıyla karşılaştır, bir çoğaltma bulunursa, listeden çıkarılır. listenin sonuna ulaşıldığında, varsa bir grup çoğaltma bulunur.

  3. Liste boş olana kadar yukarıdaki 2 adımı tekrarlayın.

En iyi durumda N-1'e ihtiyacı var, ama (N-1)! en kötü durumda.

daha iyi alternatifler nelerdir?


Yukarıda açıklanan yöntem kullanılarak kodum açıklandı:

// algorithm to consume the std::list container,
// supports: list<path_type>,list< pair<std::string, paths_type::const_iterater>>
template<class T>
struct consume_list
{
    groups_type operator()(list<T>& l)
    {
        // remove spurious identicals and group the rest
        // algorithm:  
        // 1. compare the first element with the remaining elements, 
        //    pick out all duplicated files including the first element itself.
        // 2. start over again with the shrinked list
        //     until the list contains one or zero elements.

        groups_type sub_groups;           
        group_type one_group; 
        one_group.reserve(1024);

        while(l.size() > 1)
        {
            T front(l.front());
            l.pop_front();

            item_predicate<T> ep(front);
            list<T>::iterator it     = l.begin(); 
            list<T>::iterator it_end = l.end();
            while(it != it_end)
            {
                if(ep.equals(*it))
                {
                    one_group.push_back(ep.extract_path(*(it))); // single it out
                    it = l.erase(it);
                }
                else
                {
                    it++;
                }
            }

            // save results
            if(!one_group.empty())
            {
                // save
                one_group.push_back(ep.extract_path(front));                    
                sub_groups.push_back(one_group);

                // clear, memory allocation not freed
                one_group.clear(); 
            }            
        }
        return sub_groups;
    }        
}; 


// type for item-item comparison within a stl container, e.g.  std::list 
template <class T>
struct item_predicate{};

// specialization for type path_type      
template <>
struct item_predicate<path_type>
{
public:
    item_predicate(const path_type& base)/*init list*/            
    {}
public:
    bool equals(const path_type& comparee)
    {
        bool  result;
        /* time-consuming operations here*/
        return result;
    }

    const path_type& extract_path(const path_type& p)
    {
        return p;
    }
private:
    // class members
}; 


};

Aşağıdaki cevap için teşekkürler, ancak benim örneğim tarafından tamsayılarla ilgili olarak yanıltılmış gibi görünüyorlar. Aslında öğeler tipte agnostiktir (zorunlu olarak tamsayılar, dizgiler veya diğer POD'lar)ve eşit yüklemler kendiliğinden tanımlanır, yani karşılaştırma çok ağır olabilir.

Yani belki benim sorum şu olmalıdır: Hangi veri yapısının + algoritmasının daha az karşılaştırmayı içerdiği.

Multiset gibi önceden sıralanmış bir kapsayıcı kullanarak, çoklu harita testime göre daha iyi değil,

  1. eklerken sıralama zaten karşılaştırma yapar,
  2. Aşağıdaki bitişik bulgu tekrar karşılaştırmayı yapar,
  3. Bu veri yapısı, operasyonlara eşit olmayan operasyonları tercih ediyor, 2'den daha az performans gösteriyorlar.

Karşılaştırmaları nasıl kurtaracağını göremiyorum.


Bazı cevaplar tarafından görmezden gelinen bir şey daha var, birbirinden kopya gruplarını birbirinden ayırmam gerek, sadece bunları kapta tutmak değil.


Sonuç

Tüm tartışmalardan sonra 3 yol var gibi görünüyor.

  1. yukarıda açıklandığı gibi orijinal naif metodum
  2. Gibi doğrusal bir kapsayıcıyla başla std::vector sıralayın ve sonra eşit aralıkları bulun
  3. ilgili bir kapsayıcıyla başla std::map<Type, vector<duplicates>>Charles Bailey tarafından önerildiği gibi ilgili konteyner kurulumu sırasında çiftleri seçin.

Aşağıda belirtilen tüm yöntemleri test etmek için bir örnek kodladım.

çiftlerin sayısı ve dağıtıldıklarında en iyi seçimi etkileyebilir.

  • Yöntem 1, önden ağır düştüğü zaman en iyisidir ve sonunda en kötüsüdür. Sıralama dağılımı değiştirmeyecek, ancak endian.
  • Yöntem 3 en ortalama performansa sahiptir
  • Yöntem 2 asla en iyi seçim değildir

Tartışmaya katılan herkese teşekkürler.

Aşağıdaki koddan 20 örnek öğeyle bir çıktı.

[20 10 6 5 4 3 2 2 2 2 1 ile test edin   1 1 1 1 1 1 1 1 1]

ve [1 1 1 1 1 1 1 1 1 1 2 2 2 2 3 3   Sırasıyla 4 5 6 10 20]

std :: vektör -> sort () -> kullanarak   adjacent_find ():

karşılaştırmalar: ['<' = 139, '==' = 23   ]

karşılaştırmalar: ['<' = 38, '==' = 23]

std :: list kullanarak -> sort () -> küçült   liste:

karşılaştırmalar: ['<' = 50, '==' = 43]

karşılaştırmalar: ['<' = 52, '==' = 43]

std :: list -> listesini daralt:

karşılaştırmalar: ['<' = 0, '==' = 121]

karşılaştırmalar: ['<' = 0, '==' = 43]

std :: vector -> std :: map> kullanarak:

karşılaştırmalar: ['<' = 79, '==' = 0]

karşılaştırmalar: ['<' = 53, '==' = 0]

std :: vektör kullanarak ->   std :: multiset ->   adjacent_find ():

karşılaştırmalar: ['<' = 79, '==' = 7]

karşılaştırmalar: ['<' = 53, '==' = 7]

kod

// compile with VC++10: cl.exe /EHsc

#include <vector>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
#include <sstream>

#include <boost/foreach.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/format.hpp>

using namespace std;

struct Type
{
    Type(int i) : m_i(i){}

    bool operator<(const Type& t) const
    {
        ++number_less_than_comparison;
        return m_i < t.m_i;
    }

    bool operator==(const Type& t) const
    {
        ++number_equal_comparison;    
        return m_i == t.m_i;
    }
public:
    static void log(const string& operation)
    {
        cout 
        << "comparison during " <<operation << ": [ "
        << "'<'  = " << number_less_than_comparison
        << ", "
        << "'==' = " << number_equal_comparison
        << " ]\n";

        reset();
    }

    int to_int() const
    {
        return m_i;
    }
private:
    static void reset()
    {
        number_less_than_comparison = 0;
        number_equal_comparison = 0;      
    }

public:
    static size_t number_less_than_comparison;
    static size_t number_equal_comparison;    
private:
    int m_i;
};

size_t Type::number_less_than_comparison = 0;
size_t Type::number_equal_comparison = 0;  

ostream& operator<<(ostream& os, const Type& t) 
{
    os << t.to_int();
    return os;
}

template< class Container >
struct Test
{    
    void recursive_run(size_t n)
    { 
        bool reserve_order = false;

        for(size_t i = 48; i < n; ++i)
        {
            run(i);
        }    
    }

    void run(size_t i)
    {
        cout << 
        boost::format("\n\nTest %1% sample elements\nusing method%2%:\n") 
        % i 
        % Description();

        generate_sample(i);
        sort();
        locate();   

        generate_reverse_sample(i);
        sort();
        locate(); 
    }

private:    
    void print_me(const string& when)
    {
        std::stringstream ss;
        ss << when <<" = [ ";
        BOOST_FOREACH(const Container::value_type& v, m_container)
        {
            ss << v << " ";
        }
        ss << "]\n";    
        cout << ss.str();
    }

    void generate_sample(size_t n)
    {
        m_container.clear();
        for(size_t i = 1; i <= n; ++i)
        {
            m_container.push_back(Type(n/i));    
        }
        print_me("init value");
        Type::log("setup");
    }

    void generate_reverse_sample(size_t n)
    {
        m_container.clear();
        for(size_t i = 0; i < n; ++i)
        {
            m_container.push_back(Type(n/(n-i)));     
        }
        print_me("init value(reverse order)");
        Type::log("setup");
    }    

    void sort()
    {    
        sort_it();

        Type::log("sort");
        print_me("after sort");

    }

    void locate()
    {
        locate_duplicates();

        Type::log("locate duplicate");
    }
protected:
    virtual string Description() = 0;
    virtual void sort_it() = 0;
    virtual void locate_duplicates() = 0;
protected:
    Container m_container;    
};

struct Vector : Test<vector<Type> >
{    
    string Description()
    {
        return "std::vector<Type> -> sort() -> adjacent_find()";
    } 

private:           
    void sort_it()
    {    
        std::sort(m_container.begin(), m_container.end()); 
    }

    void locate_duplicates()
    {
        using std::adjacent_find;
        typedef vector<Type>::iterator ITR;
        typedef vector<Type>::value_type  VALUE;

        typedef boost::tuple<VALUE, ITR, ITR> TUPLE;
        typedef vector<TUPLE> V_TUPLE;

        V_TUPLE results;

        ITR itr_begin(m_container.begin());
        ITR itr_end(m_container.end());       
        ITR itr(m_container.begin()); 
        ITR itr_range_begin(m_container.begin());  

        while(itr_begin != itr_end)
        {     
            // find  the start of one equal reange
            itr = adjacent_find(
            itr_begin, 
            itr_end, 
                []  (VALUE& v1, VALUE& v2)
                {
                    return v1 == v2;
                }
            );
            if(itr_end == itr) break; // end of container

            // find  the end of one equal reange
            VALUE start = *itr; 
            while(itr != itr_end)
            {
                if(!(*itr == start)) break;                
                itr++;
            }

            results.push_back(TUPLE(start, itr_range_begin, itr));

            // prepare for next iteration
            itr_begin = itr;
        }  
    }
};

struct List : Test<list<Type> >
{
    List(bool sorted) : m_sorted(sorted){}

    string Description()
    {
        return m_sorted ? "std::list -> sort() -> shrink list" : "std::list -> shrink list";
    }
private:    
    void sort_it()
    {
        if(m_sorted) m_container.sort();////std::sort(m_container.begin(), m_container.end()); 
    }

    void locate_duplicates()
    {       
        typedef list<Type>::value_type VALUE;
        typedef list<Type>::iterator ITR;

        typedef vector<VALUE>  GROUP;
        typedef vector<GROUP>  GROUPS;

        GROUPS sub_groups;
        GROUP one_group; 

        while(m_container.size() > 1)
        {
            VALUE front(m_container.front());
            m_container.pop_front();

            ITR it     = m_container.begin(); 
            ITR it_end = m_container.end();
            while(it != it_end)
            {
                if(front == (*it))
                {
                    one_group.push_back(*it); // single it out
                    it = m_container.erase(it); // shrink list by one
                }
                else
                {
                    it++;
                }
            }

            // save results
            if(!one_group.empty())
            {
                // save
                one_group.push_back(front);                    
                sub_groups.push_back(one_group);

                // clear, memory allocation not freed
                one_group.clear(); 
            }            
        }
    }        

private:
    bool m_sorted;
};

struct Map : Test<vector<Type>>
{    
    string Description()
    {
        return "std::vector -> std::map<Type, vector<Type>>" ;
    }
private:    
    void sort_it() {}

    void locate_duplicates()
    {
        typedef map<Type, vector<Type> > MAP;
        typedef MAP::iterator ITR;

        MAP local_map;

        BOOST_FOREACH(const vector<Type>::value_type& v, m_container)
        {
            pair<ITR, bool> mit; 
            mit = local_map.insert(make_pair(v, vector<Type>(1, v)));   
            if(!mit.second) (mit.first->second).push_back(v); 
         }

        ITR itr(local_map.begin());
        while(itr != local_map.end())
        {
            if(itr->second.empty()) local_map.erase(itr);

            itr++;
        }
    }        
};

struct Multiset :  Test<vector<Type>>
{
    string Description()
    {
        return "std::vector -> std::multiset<Type> -> adjacent_find()" ;
    }
private:
    void sort_it() {}

    void locate_duplicates()
    {   
        using std::adjacent_find;

        typedef set<Type> SET;
        typedef SET::iterator ITR;
        typedef SET::value_type  VALUE;

        typedef boost::tuple<VALUE, ITR, ITR> TUPLE;
        typedef vector<TUPLE> V_TUPLE;

        V_TUPLE results;

        SET local_set;
        BOOST_FOREACH(const vector<Type>::value_type& v, m_container)
        {
            local_set.insert(v);
        }

        ITR itr_begin(local_set.begin());
        ITR itr_end(local_set.end());       
        ITR itr(local_set.begin()); 
        ITR itr_range_begin(local_set.begin());  

        while(itr_begin != itr_end)
        {     
            // find  the start of one equal reange
            itr = adjacent_find(
            itr_begin, 
            itr_end, 
            []  (VALUE& v1, VALUE& v2)
                {
                    return v1 == v2;
                }
            );
            if(itr_end == itr) break; // end of container

            // find  the end of one equal reange
            VALUE start = *itr; 
            while(itr != itr_end)
            {
                if(!(*itr == start)) break;                
                itr++;
            }

            results.push_back(TUPLE(start, itr_range_begin, itr));

            // prepare for next iteration
            itr_begin = itr;
        }  
    } 
};

int main()
{
    size_t N = 20;

    Vector().run(20);
    List(true).run(20);
    List(false).run(20);
    Map().run(20);
    Multiset().run(20);
}

21
2017-08-26 08:39


Menşei


Algoritmanın amacını biraz daha iyi tanımlamanız gerektiğini düşünüyorum. Hedefin boş bir listeyle bitmek olduğu düşünüldüğünde, girişteki her şeyi en hızlı ve en basit çözüm olarak atmaz mı? - CB Bailey
giriş, olası yinelenen öğeleri içeren bir koleksiyondur ve çıkışlar, her birinin aynı türden kopyaları içeren sıfır veya daha fazla koleksiyonudur. ("Liste" terimini kullanmamayı tercih ediyorum, çünkü bazı uygulamalara işaret edebilir, örneğin std :: list) - t.g.
Bu durumda, neden önceden sıralanmış bir kapsayıcı (ör. Çoklu giriş) bir çözüm değildir. Yani post-edit, neden "bitişik bulgu" yapmak gerektiğini ima ediyorsun. Şüphesiz, konteynır doldurulduktan sonra, sadece sırayla çıktı, hiçbir karşılaştırma gerekli değil? - CB Bailey
bitişik bulguya ihtiyaç vardır çünkü çoklu tekrarlı gruplar olabilir. örneğin, {E1, E2, E2, E4, E4, E5} gibi önceden sıralanmış bir kapsayıcıda {E2, E2} ve {E4, E4} öğelerini ayırmam gerekiyor. bitişik bulgu olmadan, E2 ve E4'ün nerede başladığını ve bittiğini bilmiyorum, - t.g.
eşdeğer. ve eşdeğer olduklarını kontrol etmek, bir düzine kadar zaman alabilen pahalı işlemlerdir. Çıktı arayüzü, bilgi çıkarıldığı sürece önemli değildir. Std :: multimap uygulama sürümümde, std :: multimap :: menzili temsil eden yineleyicileri kaydettim. Çünkü std :: multimap, ekleme ve bitişik bulgudaki karşılaştırmaları içerir. Karşılaştırmaları kaydetmek umuduyla sıralanmamış bir konteyner std :: listesine geçtim. Ancak önemli bir gelişme ya da azalma yok. En az karşılaştırmalı bir algoritma ile sınırlanmış bir kapsayıcı ihtiyacım olan şeydir. - t.g.


Cevaplar:


Bir haritayı temsil edici bir öğeden diğer öğelerin bir liste / vektör / dequeine kullanabilirsiniz. Bu, konteynere yerleştirilmede nispeten daha az karşılaştırmayı gerektirir ve herhangi bir karşılaştırma yapmak zorunda kalmadan sonuçlanan gruplar arasında yineleyebileceğiniz anlamına gelir.

Bu örnek, her zaman ilk temsilci öğeyi eşlemeli deque deposuna ekler, çünkü mantıksal olarak basit bir şekilde gruptan sonraki yinelemeyi yapar, ancak bu çoğaltma bir sorunu kanıtlarsa, yalnızca push_back bir tek if (!ins_pair.second).

typedef std::map<Type, std::deque<Type> > Storage;

void Insert(Storage& s, const Type& t)
{
    std::pair<Storage::iterator, bool> ins_pair( s.insert(std::make_pair(t, std::deque<Type>())) );
    ins_pair.first->second.push_back(t);
}

Gruplar arasında geçiş yapmak (nispeten) basit ve ucuzdur:

void Iterate(const Storage& s)
{
    for (Storage::const_iterator i = s.begin(); i != s.end(); ++i)
    {
        for (std::deque<Type>::const_iterator j = i->second.begin(); j != i->second.end(); ++j)
        {
            // do something with *j
        }
    }
}

Karşılaştırma ve nesne sayımı için bazı deneyler yaptım. 50000 grubu oluşturan (yani grup başına 2 nesne ortalaması) 100000 nesne rastgele bir sınamada yapılan bir testte, yukarıdaki yöntem aşağıdaki karşılaştırmalar ve kopya sayısına mal olur:

1630674 comparisons, 443290 copies

(Kopya sayısını düşürmeyi denedim, ancak senaryonuzda daha yüksek maliyet operasyonu gibi görünen karşılaştırmalar pahasına gerçekten başardım.)

Çoklu geçişi kullanarak ve önceki geçişi grup geçişlerini algılamak için son yinelemede saklamak buna mal olur:

1756208 comparisons, 100000 copies

Tek bir listeyi kullanmak ve ön öğeyi açmak ve diğer grup üyeleri için doğrusal arama yapmak maliyeti:

1885879088 comparisons, 100000 copies

Evet, bu benim en iyi yöntem için ~ 1,6m ile karşılaştırıldığında ~ 1.9b karşılaştırmalar. Liste yönteminin optimal bir kıyaslama sayısına yakın bir yerde gerçekleştirilmesi için, sıralanması gerekirdi ve bu, ilk sırada doğal olarak sipariş edilen bir konteynerin inşa edilmesiyle benzer bir karşılaştırmaya mal olacaktı.

Düzenle

Gönderdiğiniz kodu aldım ve daha önce kullandığım gibi aynı test verisi üzerinden ima edilen algoritmayı (bazı varsayılan tanımlar gibi kod hakkında bazı varsayımlar yapmak zorunda kaldım) çalıştırdım ve saydım:

1885879088 comparisons, 420939 copies

Yani tam olarak benim aptal liste algoritmamla aynı sayıda karşılaştırma, ancak daha fazla kopya ile. Bence bu durum için esas olarak benzer algoritmalar kullanıyoruz. Alternatif sıralama düzenine dair bir kanıt göremiyorum, ancak birden fazla eşdeğer öğe içeren grupların bir listesini istediğiniz gibi görünüyor. Bu sadece benim Iterate ekleyerek işlev if (i->size > 1) fıkra.

Hala bu deformasyon haritası gibi sıralı bir konteynır inşa etmenin (optimal olmasa bile) iyi bir strateji olmadığını kanıtlayamıyorum.


2
2017-08-26 05:38



Sorunumla karşılaşmadan hemen önce benim çözümüm deque yerine liste kullandım. İşte şu soru geliyor: Artık yolunuzda önceden işlenmiş elemanlardan oluşan bir deque var, bu yüzden onlar başka öznitelikler tarafından temsil edilemezler fakat kendileri (zaten özdeş kümeleri olan dosyaları düşünün), yani eşit veya farklı olabilirler ama kendileriyle karşılaştırılması gerekir (ki bu pahalı), asgari miktardaki karşılaştırmaları kullanarak eşitleri nasıl gruplandırabilirsiniz? - t.g.
Her deque sadece eşdeğer elemanlar içerir, farklı bir kavram kullandığınızı mı söylüyorsunuz? == ve < ? - CB Bailey
Listeyi kullandım. Deque kullanacak olsaydım, ekleme öncesinde bu pahalı karşılaştırmaları yapmalıyım. İyi değil. Karşılaştırmalar çok geniş olduğu için, ertelemek için elimden gelenin en iyisini denedim (tavsiye ettiğin gibi). Şimdi yargı günü geliyor ve ben onunla yüzleşmek zorundayım - bu yüzden kıyaslama sayısını kaydetmenin yollarını arıyorum. - t.g.
Sorun, soruyu önerdiğinizden daha fazla ilgilendirir veya cevabımı yanlış anladınız. Benim cevabımda her  deque bir grup eşdeğer eleman içerir. Orijinal sorun bildirimine göre, onları sipariş etmeye gerek yoktur. Zaten sadece eşdeğer elemanlar içerirler. Artık, her gruptaki öğelerin, sipariş vermesini istediğiniz gruplardan ayıran ikinci bir alt sipariş olduğunu ima ediyorsunuz. Öyleyse, sorunu daha net hale getirmek için bu sorunu güncelleyebilir misiniz? - CB Bailey
@Charles Bailey, yoğun tartışmalar için teşekkürler ve sorumu açıklığa kavuşturmama yardımcı olun. Soruyu yeni güncelledim. Özel uygulamanızla ilgili olarak: karşılaştırma maliyeti s.insert (std :: make_pair (t, std :: deque <Type> ())) 'da gerçekleşir. Aslında, bu sayfada önerilen ttvd olarak bir B-ağacı olan std :: map pre-sorting uygulamasına güvenmeniz yeterlidir; bu, mutlaka en az karşılaştırmayı içermez. Görünen farklı elementleri filtrelemek için yolunu kullandım, Şimdi gerçek olanları bulmak için devaledeyim. Std :: list testiniz benimki gibi değil, karşılaştırırken küçülmediğiniz gibi. - t.g.


Evet, daha iyisini yapabilirsin.

  1. Onları sıralayın (basit tamsayılar için O (n), genel olarak O (n * log n)), daha sonra çiftlerin bitişik olduğu garanti edilir.

  2. Bir hash tablosu kullanın, ayrıca O (n). Her bir madde için, (a) hash tablosunda olup olmadığını kontrol edin; eğer öyleyse, bir kopyası; değilse, hash tablosuna koyun.

Düzenle

Kullandığınız yöntem O (N ^ 2) karşılaştırmaları yapıyor gibi görünüyor:

for i = 0; i < length; ++i           // will do length times
    for j = i+1; j < length; ++j     // will do length-i times
        compare

Yani uzunluk 5 için 4 + 3 + 2 + 1 = 10 karşılaştırır; 6 için 15, vb. (N ^ 2) / 2 - N / 2 olması kesin. N * log (N), N'nin makul değeri olan herhangi bir değeri için daha küçüktür.

Durumunda N ne kadar büyük?

http://img188.imageshack.us/img188/7315/foou.png

Karma çarpışmaları azaltmak için, en iyi yol daha iyi bir karma işlev elde etmektir: -D. Bunun mümkün olmadığı varsayılarak, bir varyantı (ör., Farklı bir değişiklik) yapabiliyorsanız, iç içe geçmiş bir karma yapabilirsiniz.


13
2017-08-26 05:38



benim problemim hash zaten eşittir.Ama zaten bir çarpışma kovanında olduğumuzu ve bu elemanları gruplayacağız. Eşit yüklemeli eleman her birini kurtarmak istediğim kadar pahalıysa, bunu yapmanın en iyi yolu nedir? - t.g.
Detay için teşekkürler. En kötü durumda (iki unsur eşit olmadığında),. (N ^ 2) / 2 - N / 2 bekleniyor. ama en iyi durumda (hepsi eşit olduğunda), sadece N-1 gereklidir, çünkü karşılaştırmadan sonra çekilir. Döngü sırasında elemanların silinmesinden sonra yineleyicilerin geçerli kalmasının doğası, std :: list std :: list seçimi sırasında göz önünde bulundurduğum diğer bir faktördür. - t.g.


1. O (n log n) dizisini en kötü - mergesort / heapsort / ikili ağaç sıralamasında sıralayın

2. Komşuları karşılaştırın ve maçları dışarı çekin O (n)


7
2017-08-26 05:38



ilk başta yaptığım buydu. STL std :: multimap ve std :: adjacent_find kullanarak, önemli ölçüde daha iyi değil. - t.g.
Multimap, istediğiniz performansı vermez. Tüm öğeleri bir vektöre yerleştirmek ve bunları işlendiğinde sıralamak, sıralamayı tutmak için ağaç dengelemesi yapmak zorunda olan, sıralı bir çok adımı tutmaktan daha hızlıdır. - fbrereto
@fbrereton, bu bilgi için teşekkürler, bunu test edeceğim. Muhtemelen ilk başta düşünmeden önce multimap :: euqal_range () arayüzünü almak çok kolaydı. - t.g.
Tüm STL kapsayıcılarında çalışan eşit bir algoritma vardır: cplusplus.com/reference/algorithm/equal_range - fbrereto


Karma tablo tabanlı bir yapıyı değerden saymaya devam edin; C ++ uygulamanız sunmuyorsa std::hash_map (şimdiye kadar C ++ standardının gerçekten bir parçası değil!) Boost kullanın veya web'den bir sürümü alın. Koleksiyon üzerinde bir geçiş (yani, O (N)) bir değer-> sayımı eşleştirmesi yapmanızı sağlar; Bir sayım> 1 ile değerleri tanımlamak ve uygun şekilde göndermek için karma tablo (<= O (N), açıkça) üzerinden bir kez daha geçer. Genel O (N), sizin öneriniz için geçerli değildir.


5
2017-08-26 05:38



İkinci geçişe gerek yok. Zaten içinde karma varsa, onun bir kopyası. - derobert
@derobert, evet, ama bilmiyorsun kaç sefer çoğaltılacak ve sorudaki özellikler bunu gerektiriyor. Bu yüzden ikinci bir geçiş (çözümün O (N) doğasını değiştirmez) en basit yaklaşımdır! - Alex Martelli


Sıralama yapmayı denediniz mi? Örneğin hızlı sıralama gibi bir algoritma kullanarak? Performans sizin için yeterince iyi ise o zaman bu kolay bir yaklaşım olacaktır.


1
2017-08-26 05:40





Tamsayıların bir listesi olduğu biliniyorsa ve bunların hepsi A ile B arasında olduğu biliniyorsa (örneğin A = 0, B = 9), bir B-A öğesi dizisi yapın ve B-A kapları oluşturun.

Çok özel bir durumda (düz tamsayıların listesi), sadece tam olarak saymayı öneririm çünkü farklı sayıları birbirinden ayırt edemezsiniz:

for(int i = 0; i < countOfNumbers; i++)
    counter[number[i]]++;

Eğer onlar Hangi ayırt edilebilir, bir dizi liste oluşturun ve bunları ilgili listeye ekleyin.

Sayı değilse, std :: map veya std :: hash_map, eşleme anahtarlarını değer listelerine kullanın.


1
2017-08-26 05:39





En basit olanı muhtemelen listeyi sıralamak ve daha sonra yineleme yapmak için tekrarlamaktır.

Veriler hakkında bir şey biliyorsanız, daha verimli algoritmalar mümkündür.

Örneğin, listenin büyük olduğunu ve n'nin oldukça küçük olduğu 1.n'den yalnızca tamsayılar olduğunu biliyorsanız, bir çift boole dizisi (veya bir bitmap) kullanabilir ve böyle bir şey yapabilirsiniz:

bool[] once = new bool[MAXIMUM_VALUE];
bool[] many = new bool[MAXIMUM_VALUE];
for (int i = 0; i < list.Length; i++)
    if (once[ value[i] ])
        many[ value[i] ] = true;
    else
        once[ value[i] ] = true;

Şimdi, birçok [], bir kereden fazla değerlerin görüldüğü bir dizi içerir.


0
2017-08-26 06:17





Hash / sırasız harita çözümlerinden bahseden çoğu insan O (1) ekleme ve sorgulama zamanını varsaymaktadır, ancak O (N) en kötü durum olabilir. Ek olarak, nesne karmaşasının maliyetini geçersiz kılarsınız.

Şahsen ben (her biri için O (logn) ekleme) bir ikili ağaç içine nesneleri sokmak ve her düğümde karşı durmak. Bu, tüm kopyaları tanımlamak için O (nlogn) yapım süresini ve O (n) geçişini sağlayacaktır.


0
2017-08-27 10:06



Diğer cevaplar hakkında veri yapısının yapım maliyetini görmezden gelmek ve sadece belirli veri yapısına bağlı algoritma yararını ölçmek hakkına sahipsiniz. Sizin yönteminiz sadece std :: haritasının uygulanması mı? Bir veri yapısını seçmenin, enine bir algoritmanın daha önemli olduğunun diğerleriyle olduğun anlaşılıyor. - t.g.
Aslında. Özür dilerim, orijinal sorunuzda yorum bırakamıyorum. Listenizdeki her nesne türü için boş bir koleksiyon (liste) oluşturmak mümkün mü (tüm E2'ler için bir tane, tüm E3'ler için bir tane, vs.)? Eğer öyleyse, nesne setini doğrusal olarak hareket ettirebilir ve nesneye bağlı olarak ilgili "depolama listesini" bulabilir ve buraya ekleyebilirsiniz. Bu karşılaştırmaları engeller ve uygulamanıza bağlı olarak bu O (N) 'de uygulanabilir. - ttvd
Sanırım Charles Bailey'e benzer bir şey öneriyorsun. Gerçekten bunu neredeyse eşit unsurları gruplamak için bir ön adım olarak yaptım. ve sonra benim problemim ortaya çıkıyor, karşılaştırmayı diğer türlere devretemiyorum, ama kendileri ve tabii ki pahalılar. Bu yüzden, karşılaştırmaların sayısını kaydetmek için bir yol arıyorum çünkü onlarla uğraşmanın bir yolu yok. - t.g.