Najszybsze narzędzie do prostych ale czasochłonnych obliczeń.

Cześć - spędzam ostatnio dość dużo czasu z excelem - robię różne obliczenia ale pojawił się się problem gdy zacząłem działać na bardzo dużej ilości danych - excel działa przez to bardzo wolno i chciałem się wspomóc jakimś programikiem/skryptem który by mi proste ale czasochłonne obliczenia znacznie szybciej zliczył a resztę już bym sobie w excelu dokończył.

Spróbuję zapytać na forum i może ktoś akurat ktoś poratuje mnie jakimś ciekawym rozwiązaniem - oczywiście jeśli prośba moja nie jest strasznie trudna do zrealizowania.

Więc w skrócie chodzi o to że mam np. 100 000 zbiorów liczb - powiedzmy w każdym jest od 2 do max 60 liczb.

Zbiór nr 1: 1,2,3,4,5,6,7,8,9
Zbiór nr 2: 10,11,12,13,14
Zbiór nr 3: 20,21,22,23
itd

I mam np. 100 000 różnych mniejszych zbiorów - np

1. 1,2,3
2. 1,2,10,11
3. 3,4,21,22,23
   itd

I teraz tak - do każdego większego zbioru ustawiam sobie wartość MAX - czyli że ze zbioru nr 1 można wybrać max 1 liczbę, ze zbioru 2 max 1 a ze zbioru 3 max 2 liczby itd

I chodzi mi to aby program sprawdził ile błędów ma każdy mały zbiór - czyli jeśli ustawię tak:

Zbiór nr 1: 1,2,3,4,5,6,7,8,9 - max 1 liczba
Zbiór nr 2: 10,11,12,13,14 - max 1 liczba
Zbiór nr 3: 20,21,22,23 - max 2 liczby

to:

1. 1,2,3 - błędy: 1 - bo jest za dużo liczb z 1 zbioru
2. 1,2,10,11 - błędy: 2 - bo jest za dużo liczb z 1 i 2 zbioru
3. 3,4,21,22,23 - błędy: 2 - bo jest za dużo liczb z 1 i 3 zbioru

Jakoś to sobie w excelu zrobiłem ale działa to strasznie wolno - liczy kilka godzin a wiem że za pomocą programowania można takie obliczenia zrobić w kilkadziesiąt minut - a może i szybciej - niestety nie ma zielonego pojęcia o żadnym języku programowania więc nie wiem czy stworzenie narzędzia do takich obliczeń jest trudne więc zapytam na forum i z góry dziękuję za pomoc jeśli taka się pojawi :)

Jeśli dobrze rozumiem twój problem to jest trywialny.
Dla każdego zbioru (tego dużego)
liczysz sobie przecięcia zbioru z każdym z małych zbiorów i sprawdzasz ile elementów ma to przecięcie a następnie porównujesz je z tym swoim MAX i jeśli jest > to inkrementujesz licznik błędów

Efektywnie to jest algorytm na O(n^2) więc powinien policzyć się bez problemów w krótkim czasie.
edit: dla jasności to to jest program do napisania w max 30 linijkach w jakimś pythonie ;) Moglibyśmy nawet zrobić konkurs z serii "kto napisze krócej" ;]

to dobrze że nie jest to skomplikowane do napisania - będę bardzo wdzięczny za pomoc :)

Przesadziłem z 30 linijkami ;] Program zakłada że:

• w pliku z dużymi setami ostatnia liczba w linii określa "max"

def main():
	sets = []
	small_sets=[]
	with open("zbiory.txt") as file:
	  for line in file:
		numbers = map(int,line.split(','))
		sets.append((set(numbers[:-1]),numbers[-1:][0]))
	with open("zbiory_male.txt") as file:
		small_sets = [set(map(int,line.split(','))) for line in file]

	for index,small_set in enumerate(small_sets):
	  errors = []
	  for large_index, (large_set,max) in enumerate(sets):
		if len(large_set & small_set) > max:
		  errors.append(large_index)
	  print("In set %s there were %s errors, in: %s" % (index,len(errors),errors))
main()

super - niedługo sprawdze jak działa - tylko nie wiem czy dobrze sie zrozumielismy - wartosc max mozna ustawic tylko jedna, taka sama dla wszystkich zbiorow, czy dla kazdego zbioru mozna ustawic inny max ? Bo chodzi mi o drugie rozwiazanie.

Rozwiązanie w C#.

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication1
{
    public class Program
    {
        private static void Main(string[] args)
        {
            SetCollection withMax = new SetCollection();
            withMax.Add(1, new[]{1,2,3,4,5,6,7,8,9});
            withMax.Add(1, new[]{10,11,12,13,14});
            withMax.Add(2, new[]{20,21,22,23});

            List<int[]> withoutMax = new List<int[]>();
            withoutMax.Add(new[]{1,2,3});
            withoutMax.Add(new[]{1,2,10,11});
            withoutMax.Add(new[]{3,4,21,22,23});

            var errors = ErrorsCount(withMax, withoutMax);
            for (int i = 0; i < errors.Length; i++)
            {
                Console.Write("{0}. ", i+1);
                foreach (var value in withoutMax[i])
                {
                    Console.Write("{0} ", value);
                }
                Console.WriteLine("\t\tbłędy: {0}", errors[i]);
            }
            Console.ReadLine();
        }

        public static int[] ErrorsCount(SetCollection setsWithMax, List<int[]> setsWithoutMax)
        {
            int[] errorCounts = new int[setsWithoutMax.Count];

            for (int i = 0; i < setsWithoutMax.Count; i++)
            {
                var withoutMax = setsWithoutMax[i];
                foreach (var withMax in setsWithMax)
                {
                    if (withoutMax.Intersect(withMax).Count() > withMax.Maximum)
                        errorCounts[i]++;
                }
            }

            return errorCounts;
        }

        public class SetCollection : List<SetWithMaximum>
        {
            public void Add(int maximum, IEnumerable<int> array)
            {
                this.Add( new SetWithMaximum(maximum,array));
            }
        }
        
        public class SetWithMaximum : List<int> 
        {
            public int Maximum;
            public SetWithMaximum(int maximum, IEnumerable<int> array) : base(array)
            {
                Maximum = maximum;
            }
        }
    }
}

sadasdzx - jeśli mam kilkadziesiąt tysięcy zbiorów to muszę je ręcznie wstawić do kodu ?

Shalom - nie wiem co źle robię, gdy dodałem zbiory w plikach txt to po uruchomieniu wyskakuje błąd:

 "Traceback (most recent call last):
  File "C:/Users/Admin/Desktop/zbiory.py", line 17, in <module>
    main()
  File "C:/Users/Admin/Desktop/zbiory.py", line 7, in main
    sets.append((set(numbers[:-1]),numbers[-1:][0]))
TypeError: 'map' object is not subscriptable" 

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace ConsoleApplication1
{
    public class Program
    {
        private static void Main(string[] args)
        {
            SetCollection withMax = LoadSetsWithMax("withmax.txt");
            List<int[]> withoutMax = LoadSetsWithoutMax("withoutmax.txt");

            var errors = ErrorsCount(withMax, withoutMax);
            for (int i = 0; i < errors.Length; i++)
            {
                Console.Write("{0}. ", i+1);
                foreach (var value in withoutMax[i])
                {
                    Console.Write("{0} ", value);
                }
                Console.WriteLine("\t\tbłędy: {0}", errors[i]);
            }
            Console.ReadLine();
        }

        public static IEnumerable<int> LineToInts(string line)
        {
            return line.Split(new char[] {' '}, StringSplitOptions.RemoveEmptyEntries).Select(s => int.Parse(s));
        }

        public static SetCollection LoadSetsWithMax(string filename)
        {
            var lines = File.ReadAllLines(filename);

            var collection = new SetCollection();

            foreach (var line in lines)
            {
                var numbers = LineToInts(line);
                collection.Add(numbers.ElementAt(0), numbers.Skip(1));
            }

            return collection;
        }

        public static List<int[]> LoadSetsWithoutMax(string filename)
        {
            var lines = File.ReadAllLines(filename);

            var collection = new List<int[]>();

            foreach (var line in lines)
            {
                collection.Add( LineToInts(line).ToArray());
            }

            return collection;
        }
        public static int[] ErrorsCount(SetCollection setsWithMax, List<int[]> setsWithoutMax)
        {
            int[] errorCounts = new int[setsWithoutMax.Count];

            for (int i = 0; i < setsWithoutMax.Count; i++)
            {
                var withoutMax = setsWithoutMax[i];
                foreach (var withMax in setsWithMax)
                {
                    if (withoutMax.Intersect(withMax).Count() > withMax.Maximum)
                        errorCounts[i]++;
                }
            }

            return errorCounts;
        }

        public class SetCollection : List<SetWithMaximum>
        {
            public void Add(int maximum, IEnumerable<int> array)
            {
                this.Add( new SetWithMaximum(maximum,array));
            }
        }
        
        public class SetWithMaximum : List<int> 
        {
            public int Maximum;
            public SetWithMaximum(int maximum, IEnumerable<int> array) : base(array)
            {
                Maximum = maximum;
            }
        }
    }
}

Withmax.txt - pierwsza liczba = max, kolejne to zbiór.

1 1 2 3 4 5 6 7 8 9
1 10 11 12 13 14
2 20 21 22 23

withoutmax.txt - po prostu zbiór.

1 2 3
1 2 10 11
3 4 21 22 23

super już sprawdzam :)

W C++ wygląda to tak. Pewnie da się krócej używając STLa jednak ja nie znam go jeszcze za dobrze.

#include <iostream>
#include <vector>
using namespace std;
void asd(vector<vector<int> >& big, vector<vector<int> >& small, vector<int>& result) //pierwsza liczba w każdym z dużych zbiorów okresla max
{
    for(int i = 0, errors = 0; i < small.size(); ++i, result.push_back(errors), errors = 0)
        for(int j = 0; j < big.size(); ++j)
            for(int max = big[j][0], now = 0, offsetSmall = 0, offsetBig = 0;;)
            {
                if(now > max || offsetBig >= big[j].size() || offsetSmall >= small[i].size()) {errors += (now > max); break;}
                while(big[j][offsetBig] > small[i][offsetSmall] && offsetSmall < small[i].size()) ++offsetSmall;
                while(big[j][offsetBig] < small[i][offsetSmall] && offsetBig < big[j].size()) ++offsetBig;
                if(big[j][offsetBig] == small[i][offsetSmall]) ++now, ++offsetBig;
            }
}
int main()
{
    vector<vector<int> > big;
    vector<vector<int> > small;
    vector<int> result;
    vector<int> tmp;
    tmp.push_back(1);
    for(int i = 1; i <= 9; ++i) tmp.push_back(i);
    big.push_back(tmp);
    tmp.clear();
    tmp.push_back(1);
    for(int i = 10; i <= 14; ++i) tmp.push_back(i);
    big.push_back(tmp);
    tmp.clear();
    tmp.push_back(2);
    for(int i = 20; i <= 23; ++i) tmp.push_back(i);
    big.push_back(tmp);
    tmp.clear();


    for(int i = 1; i <= 3; ++i) tmp.push_back(i);
    small.push_back(tmp);
    tmp.clear();
    for(int i = 1; i <= 2; ++i) tmp.push_back(i);
    for(int i = 10; i <= 11; ++i) tmp.push_back(i);
    small.push_back(tmp);
    tmp.clear();
    for(int i = 3; i <= 4; ++i) tmp.push_back(i);
    for(int i = 21; i <= 23; ++i) tmp.push_back(i);
    small.push_back(tmp);
    tmp.clear();

    asd(big, small, result);

    for(int i = 0; i < result.size(); ++i)cout << result[i] << '\n';
    return 0;
}

Wydaje mi się, że ważna jest sama funkcja. Przygotowanie danych można zrobić w zależności od potrzeby.
Przepraszam jeśli uraziłem kogoś tak brzydkim wypełnianiem tych vectorów ;d (nie mam pod ręką kompilatora z C++11).

sadasdzx -> jakiego programu najlepiej użyć ? póki co w notepadzie nie udało mi się uruchomić tego kodu (zapisałem jako bat i może to błąd) - ściągam teraz visual C++...
Sopelek -> wstawianie danych też u Ciebie odbywa się za pomocą plików txt ?

ok to ktoś mi doradzi co robię źle - dlaczego wyskakuje mi błąd który wyżej wstawiłem stosując rozwiązanie Shalom'a ?

ten błąd:

 "Traceback (most recent call last):
  File "C:/Users/Admin/Desktop/zbiory.py", line 17, in <module>
    main()
  File "C:/Users/Admin/Desktop/zbiory.py", line 7, in main
    sets.append((set(numbers[:-1]),numbers[-1:][0]))
TypeError: 'map' object is not subscriptable" 

Przy założeniu: wszystkie liczby z zakresu 1..64
będzie działać nawet to (30 linijek zgodnie z przewidywaniami @Shalom):

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
using namespace std;

bool readset(istream &s,unsigned long long &set)
  {
   static const unsigned long long one=1;
   bool ok=false;
   set=0;
   string line;
   if(getline(s,line))
     {
      istringstream sin(line);
      for(unsigned num;sin>>num;set|=(one<<(num-1))) ok=true;
     }
   return ok;
  }

int main()
  {
   ifstream Short("short.txt"),Long("long.txt");
   for(unsigned long long S;readset(Short,S);Long.clear(),Long.seekg(0))
     {
      unsigned Err=0,max;
      for(unsigned long long L;readset(Long>>max,L);Err+=((L)&&(!max))) for(L&=S;(L)&&(max);L&=(L-1)) --max;
      cout<<"Bledy "<<Err<<endl;
     }
   return 0;
  }

Plik long.txt (max jest pierwszą liczbą w wierszu)

1 1 2 3 4 5 6 7 8 9
1 10 11 12 13 14
2 20 21 22 23

Plik short.txt:

1 2 3
1 2 10 11
3 4 21 22 23

endriuuu żeby skompilować mój kod potrzebujesz kompilatora do C#, ściągnij Visual Studion 2012 Express.

_13th_Dragon: skąd wziąłeś założenie że liczby są od 1 do 64? Autor napisał że liczb może być do 60 nie wspominając o ich wartości.

a wersja 2010 może być ?
założenie Dragona jest słuszne :)

endriuuu napisał(a):

a wersja 2010 może być ?
założenie Dragona jest słuszne :)

Może być, ale skoro dragon zgadł to użyj jego rozwiązania będzie znacznie szybsze.

vpiotr: chyba coś Ci się pomieszało.

dobra skompilowałem i pojawił się w folderze debug plik zbiory.exe i gdy go włączam to wyskakuje mi konsola z wynikami:
Bledy 1,
Bledy 2
Bledy 2
ale jak zapisać to do pliku tekstowego tak abym sobie to posegregował w excelu w takiej postaci:
1 2 3 - 1
1 2 10 11 - 2
3 4 21 22 23 - 2

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
using namespace std;
 
bool readset(istream &s,unsigned long long &set,bool show=false)
  {
   static const unsigned long long one=1;
   bool ok=false;
   set=0;
   string line;
   if(getline(s,line))
     {
      istringstream sin(line);
      for(unsigned num;sin>>num;set|=(one<<(num-1))) { ok=true; if(show) cout<<num<<' '; }
     }
   return ok;
  }
 
int main()
  {
   ifstream Short("short.txt"),Long("long.txt");
   for(unsigned long long S;readset(Short,S,true);Long.clear(),Long.seekg(0))
     {
      unsigned Err=0,max;
      for(unsigned long long L;readset(Long>>max,L);Err+=((L)&&(!max))) for(L&=S;(L)&&(max);L&=(L-1)) --max;
      cout<<"- "<<Err<<endl;
     }
   return 0;
  }

dobra rozwiązanie podane przez _13th_Dragon już działa prawidłowo - niestety - działa trochę wolno - liczy około 100 linijek na 5-6 sekund - czyli przy ilości 100 000 linijek jest to prawie 2h - chyba że coś źle zrobiłem ...
Może sposób podany przez Shalom'a będzie szybszy jak uda mi się go uruchomić ...

Rozwiązanie w Haskellu

import Data.Set(Set, intersection, fromList, size)

errors :: (Ord a) => [(Int,Set a)] -> [Set a] -> [Int]
errors longs shorts = [ sum es | s <- shorts, let es = map (errs s) longs ]
  where errs s (max,l) = let x = size $ s `intersection` l
                         in fromEnum $ x > max

main = do
  long <- readFile "long.txt"
  short <- readFile "short.txt"
  let readMany = map (map read . words) . lines
      h (x:xs) = (x, fromList xs)
      longs = map h . readMany $ long
      shorts = map fromList . readMany $ short
      es = errors longs shorts
  mapM_ print . filter ((>0) . snd) . zip [1..] $ es

Dla plików wejściowych (pierwsza liczba w pliku long.txt to maksimum):
long.txt

1 1 2 3 4 5 6 7 8 9
1 10 11 12 13 14
2 20 21 22 23

short.txt

1 2 3
1 2 10 11
3 4 21 22 23

otrzymujemy rozwiązanie w formacie (numer małego zbioru, liczba błędów)

(1,1)
(2,2)
(3,2)

Aby skompilować ten program potrzebujesz Haskell Platform. Jeśli nie chce Ci się pobierać całego pakietu dla jednego programu, w załączniku zamieszczam skompilowany plik .exe.

http://www.speedyshare.com/jYgtE/Release.zip

Tu jest skompilowane z C#, jak sprawdzałem, to zbiór z 10 000 maksimum x 100 000 "krótkich" setów liczył w 100s.

@endriuuu a odpalałeś to pythonem 2 czy 3? Pod 2.7 nie mam żadnych problemów z tym kodem ale pod 3 też nie powinno być problemów.
Przy czym wątpię żeby działało to szybciej od kodów w językach kompilowanych ;)

Wydaje mi się że szybszego nie da się zrobić:

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <list>
using namespace std;

typedef pair<unsigned,unsigned long long> DATA;
typedef list<DATA> LIST;

bool readset(istream &s,unsigned long long &set,bool show=false)
  {
   static const unsigned long long one=1;
   bool ok=false;
   set=0;
   string line;
   if(getline(s,line))
     {
      istringstream sin(line);
      for(unsigned num;sin>>num;set|=(one<<(num-1)))
        {
         if(show) cout<<num<<' ';
         ok=true;
        }
     }
   return ok;
  }

int main()
  {
   ifstream Short("short.txt"),Long("long.txt");
   LIST lst;
   unsigned long long S;
   unsigned max;
   while(readset(Long>>max,S)) lst.push_back(DATA(max,S));
   while(readset(Short,S,true))
     {
      unsigned Err=0;
      for(LIST::iterator i=lst.begin();i!=lst.end();++i)
        {
         max=i->first;
         unsigned long long L=i->second;
         for(L&=S;(L)&&(max);L&=(L-1)) --max;
         Err+=((L)&&(!max));
        }
      cout<<"- "<<Err<<endl;
     }
   return 0;
  }

Oak - dzięki za pomoc - działa bardzo szybko i liczy poprawnie :)

sasasaas -> wooow - działa piekielnie szybko = również wielkie dzięki za pomoc - ale nie wiem czemu każdy mały zbiór ma o 1 mniej błędów niż w excelu - sprawdzałem kilka razy i nie wiem o co chodzi - jeśli możesz to sprawdź czy nie trzeba zrobić małej poprawki - używam te same dane w pliku Oak i u Ciebie i po uruchomieniu Twojego programu każdy mały zbiór ma błędów o jeden mniej (-1) ...

Pobawiłem się jeszcze trochę z tym kodem i lekko zoptymalizowałem.

import Data.IntSet(IntSet, intersection, fromList, size)
import Control.Parallel.Strategies
import GHC.Conc(numCapabilities)

errors :: [(Int,IntSet)] -> [IntSet] -> [Int]
errors longs shorts = [ sum es | s <- shorts, let es = map (errs s) longs ]
  where errs s (max,l) = let x = size $ s `intersection` l
                         in fromEnum $ x > max

main = do
  long <- readFile "long.txt"
  short <- readFile "short.txt"
  let readMany = map (map read . words) . lines
      h (x:xs) = (x, fromList xs)
      longs = map h . readMany $ long
      shorts = map fromList . readMany $ short
      chunks = 1 + (length shorts `div` numCapabilities)
      es = errors longs shorts `using` parListChunk chunks rdeepseq
  mapM_ print es

Tym razem program wykorzystuje wszystkie dostępne rdzenie procesora.
Mimo wszystko dla dużych danych wejściowych zdecydowana większość czasu spędzana jest na liczeniu linijki

x = size $ s `intersection` l

i nie wiem jak można ją przyspieszyć.

Zmieniłem format wyjścia: teraz wypisywana jest po prostu liczba błędów dla danego zbioru (po kolei).
W załączniku plik wykonywalny.
Gdyby ktoś chciał kompilować sam trzeba pamiętać o opcjach kompilacji, które pozwolą na wykorzystanie wielu rdzeni.
ghc -O2 -threaded -fforce-recomp -with-rtsopts=-N zbiory.hs

Dla zabawy napisałem wersję w Scala.

::#!
@echo off
call scala %0 %*
goto :eof
::!#
// scala.bat
import scala.io.Source
	
val longLines = Source.fromFile("long.txt").getLines().toList
val shortLines = Source.fromFile("short.txt").getLines().toList

val longSetsWithMax = for (longLine <- longLines) 
	yield longLine.split("[ \t]+") match { case Array(max, nums @ _*) => (max.toInt, nums.map(_.toInt).toSet) }
val shortSets = for (shortLine <- shortLines) 
	yield shortLine.split("[ \t]+") match { case Array(nums @ _*) => nums.map(_.toInt).toSet }	

val shortSetsWithErrNum = for (shortSet <- shortSets) 
	yield (shortSet, longSetsWithMax.count((t: (Int, Set[Int])) => t._1 < (t._2 & shortSet).size))

shortSetsWithErrNum map println

Skrypt zbyt czytelny nie jest, ale nie mam już czasu go dopieścić ;)