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

Rejestracja:prawie 12 lat
Ostatnio:ponad 10 lat
Postów:26

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,2,3
1,2,10,11
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,2,3 - błędy: 1 - bo jest za dużo liczb z 1 zbioru
1,2,10,11 - błędy: 2 - bo jest za dużo liczb z 1 i 2 zbioru
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 :)

edytowany 2x, ostatnio: flowCRANE 2013-05-31 21:19

Shalom

2013-05-31 20:53

~~Shalom~~2013-05-31 20:53

Rejestracja:około 21 lat
Ostatnio:prawie 3 lata
Lokalizacja:Space: the final frontier
Postów:26433

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" ;]

edytowany 1x, ostatnio: ~~Shalom~~ 2013-05-31 20:57

Sopelek 2013-05-31 22:04

Ja dla odmiany spróbuję w C++ ;p. Jutro się zobaczy czy coś z tego będzie.

~~vpiotr~~ 2013-06-01 09:05

Tu są dostępne 4 wymiary, więc coś nie halo z tym n^2. n - liczba zbiorów "dużych", k - liczba zbiorów "małych", n(i) - długość zbioru dużego i, k(j) - długość zbioru małego j, złożoność będzie jakoś tak n * k * SUM(n(i)) * AVG(k(j)) - średnio w środku małego zbioru można przerwać skanowanie dużego. Nawet jeśli n = k to złożoność optymalna nie jest kwadratowa.

~~Shalom~~ 2013-06-01 13:41

A ktoś mówił o optymalnej złożoności? Podałem złożoność podanego przez siebie algorytmu tylko. W pesymistycznym przypadku ma on O(n^2)

~~vpiotr~~ 2013-06-01 14:59

Nie chce się czepiać, ale patrz tytuł wątku...

endriuuu

2013-05-31 21:30

endriuuu2013-05-31 21:30

Rejestracja:prawie 12 lat
Ostatnio:ponad 10 lat
Postów:26

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

edytowany 1x, ostatnio: endriuuu 2013-05-31 21:48

Shalom

2013-05-31 22:27

~~Shalom~~2013-05-31 22:27

Rejestracja:około 21 lat
Ostatnio:prawie 3 lata
Lokalizacja:Space: the final frontier
Postów:26433

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

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

Kopiuj

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()

edytowany 1x, ostatnio: ~~Shalom~~ 2013-06-01 13:34

~~vpiotr~~ 2013-06-01 09:09

Tu jest o tyle nieoptymalnie że najpierw robisz przecięcie dużego z małym zbiorem a potem liczysz liczebność tego przecięcia. Dla pary (duży-zbior, mały-zbior) wystarczy skanować dopóki nie znajdziesz wystarczająco (>MAX) wspólnych elementów, czyli zamiast stałego nk można zeskanować od n do nk elementów. Nie znam na tyle Pythona żeby to optymalnie poprawić.

endriuuu

2013-06-01 05:03

endriuuu2013-06-01 05:03

Rejestracja:prawie 12 lat
Ostatnio:ponad 10 lat
Postów:26

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.

~~Shalom~~ 2013-06-01 13:33

Dla każdego inne, chodziło mi oczywiście o ostatnią liczbę w linii a nie w pliku ;)

sadasdzx

2013-06-01 06:59

sadasdzx2013-06-01 06:59

Rozwiązanie w C#.

Kopiuj

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;
            }
        }
    }
}

endriuuu

2013-06-01 07:38

endriuuu2013-06-01 07:38

Rejestracja:prawie 12 lat
Ostatnio:ponad 10 lat
Postów:26

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:

Kopiuj

 "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"

sadasdzx

2013-06-01 07:54

sadasdzx2013-06-01 07:54

Kopiuj

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.

Kopiuj

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.

Kopiuj

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

endriuuu

2013-06-01 08:00

endriuuu2013-06-01 08:00

Rejestracja:prawie 12 lat
Ostatnio:ponad 10 lat
Postów:26

super już sprawdzam :)

Sopelek

2013-06-01 08:30

Sopelek2013-06-01 08:30

Rejestracja:prawie 13 lat
Ostatnio:ponad 8 lat
Lokalizacja:Kraków
Postów:467

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

Kopiuj

#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).

edytowany 3x, ostatnio: Sopelek 2013-06-01 08:34

endriuuu

2013-06-01 08:43

endriuuu2013-06-01 08:43

Rejestracja:prawie 12 lat
Ostatnio:ponad 10 lat
Postów:26

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 ?

Sopelek 2013-06-01 08:49

U mnie dane są wpisane na sztywno. Nie przejmowałem się tym, bo @Shalom dał ci pełne rozwiązanie razem z wczytywaniem. Ja skupiłem się jedynie na algorytmie.

endriuuu

2013-06-01 08:53

endriuuu2013-06-01 08:53

Rejestracja:prawie 12 lat
Ostatnio:ponad 10 lat
Postów:26

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:

Kopiuj

 "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"

edytowany 1x, ostatnio: endriuuu 2013-06-01 08:53

_13th_Dragon

2013-06-01 09:02

_13th_Dragon2013-06-01 09:02

Rejestracja:ponad 19 lat
Ostatnio:2 miesiące

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

Kopiuj

#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)

Kopiuj

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

Plik short.txt:

Kopiuj

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

edytowany 2x, ostatnio: _13th_Dragon 2013-06-01 09:02

~~vpiotr~~ 2013-06-01 09:34

Czy nie powinno być "L = L >> 1" zamiast "L&=(L-1)" ?

_13th_Dragon 2013-06-01 09:43

Nie. L&=(L-1) - usuwa z L jedną jedynkę niezależnie od tego na której pozycji ona jest.

~~vpiotr~~ 2013-06-01 10:12

Fajne, nie znałem tego (albo zapomniałem).

asddasasdzxczxc

2013-06-01 09:21

asddasasdzxczxc2013-06-01 09:21

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.

endriuuu

2013-06-01 09:24

endriuuu2013-06-01 09:24

Rejestracja:prawie 12 lat
Ostatnio:ponad 10 lat
Postów:26

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

asddasasdzxczxc

2013-06-01 09:26

asddasasdzxczxc2013-06-01 09:26

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.

endriuuu

2013-06-01 09:49

endriuuu2013-06-01 09:49

Rejestracja:prawie 12 lat
Ostatnio:ponad 10 lat
Postów:26

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

edytowany 5x, ostatnio: endriuuu 2013-06-01 10:00

Sopelek 2013-06-01 09:54

uruchom go z poziomu konsoli

_13th_Dragon 2013-06-01 10:04

jw plus odpalić: zbiory>wynik.xls

_13th_Dragon

2013-06-01 10:01

_13th_Dragon2013-06-01 10:01

Rejestracja:ponad 19 lat
Ostatnio:2 miesiące

Kopiuj

#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;
  }

edytowany 1x, ostatnio: _13th_Dragon 2013-06-01 10:15

endriuuu 2013-06-01 10:12

wyskakują mi błędy: error C2061: syntax error : identifier 'show' error C2065: 'show' : undeclared identifier error C2660: 'readset' : function does not take 3 arguments

_13th_Dragon 2013-06-01 10:16

poprawiłem.

endriuuu

2013-06-01 10:44

endriuuu2013-06-01 10:44

Rejestracja:prawie 12 lat
Ostatnio:ponad 10 lat
Postów:26

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ć ...

n0name_l 2013-06-01 12:42

Co do kodu wyzej: zamien strumienia c++ na fprintf/fscanf bo prawdopodobnie wiekszosc czasu zzeraja operacje na plikach. Co do kodu Shalom(a) sciagnij pythona i odpal.

Oak

2013-06-01 12:44

Oak2013-06-01 12:44

Rejestracja:ponad 13 lat
Ostatnio:prawie 10 lat
Postów:95

Rozwiązanie w Haskellu

Kopiuj

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

Kopiuj

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

short.txt

Kopiuj

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)

Kopiuj

(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.

zbiory.zip (277 KB) - ściągnięć: 53

sasasaas

2013-06-01 13:08

sasasaas2013-06-01 13:08

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.

Shalom

2013-06-01 13:39

~~Shalom~~2013-06-01 13:39

Rejestracja:około 21 lat
Ostatnio:prawie 3 lata
Lokalizacja:Space: the final frontier
Postów:26433

@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 ;)

edytowany 1x, ostatnio: ~~Shalom~~ 2013-06-01 13:41

endriuuu 2013-06-01 15:18

mam wersje 3.3

_13th_Dragon

2013-06-01 14:33

_13th_Dragon2013-06-01 14:33

Rejestracja:ponad 19 lat
Ostatnio:2 miesiące

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

Kopiuj

#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;
  }

endriuuu

2013-06-01 15:30

endriuuu2013-06-01 15:30

Rejestracja:prawie 12 lat
Ostatnio:ponad 10 lat
Postów:26

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) ...

Oak

2013-06-01 16:50

Oak2013-06-01 16:50

Rejestracja:ponad 13 lat
Ostatnio:prawie 10 lat
Postów:95

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

Kopiuj

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

Kopiuj

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

zbiory.zip (287 KB) - ściągnięć: 36

Ekstrapolowany

2013-06-01 21:47

Ekstrapolowany2013-06-01 21:47

Rejestracja:prawie 13 lat
Ostatnio:prawie 7 lat
Postów:4

Dla zabawy napisałem wersję w Scala.

Kopiuj

::#!
@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ć ;)

Liczba odpowiedzi na stronę

Treść *

Treść

Podgląd

Kliknij, aby dodać treść...

Kliknij, aby dodać załącznik lub wklej ze schowka.

Instrukcja obsługi Markdown

Pomoc 1.18.8

Typografia

Edytor obsługuje składnie Markdown, w której pojedynczy akcent *kursywa* oraz _kursywa_ to pochylenie. Z kolei podwójny akcent **pogrubienie** oraz __pogrubienie__ to pogrubienie. Dodanie znaczników ~~strike~~ to przekreślenie.

Możesz dodać formatowanie komendami , , oraz .

Ponieważ dekoracja podkreślenia jest przeznaczona na linki, markdown nie zawiera specjalnej składni dla podkreślenia. Dlatego by dodać podkreślenie, użyj underline.

Komendy formatujące reagują na skróty klawiszowe: Ctrl+B, Ctrl+I, Ctrl+U oraz Ctrl+S.

Linki

By dodać link w edytorze użyj komendy lub użyj składni [title](link). URL umieszczony w linku lub nawet URL umieszczony bezpośrednio w tekście będzie aktywny i klikalny.

Jeżeli chcesz, możesz samodzielnie dodać link: <a href="link">title</a>.

Wewnętrzne odnośniki

Możesz umieścić odnośnik do wewnętrznej podstrony, używając następującej składni: [[Delphi/Kompendium]] lub [[Delphi/Kompendium|kliknij, aby przejść do kompendium]]. Odnośniki mogą prowadzić do Forum 4programmers.net lub np. do Kompendium.

Wspomnienia użytkowników

By wspomnieć użytkownika forum, wpisz w formularzu znak @. Zobaczysz okienko samouzupełniające nazwy użytkowników. Samouzupełnienie dobierze odpowiedni format wspomnienia, zależnie od tego czy w nazwie użytkownika znajduje się spacja.

Znaczniki HTML

Dozwolone jest używanie niektórych znaczników HTML: <a>, , , <kbd>, <del>, , <dfn>, <pre>, <blockquote>, <hr/>, ,  oraz <img/>.

Skróty klawiszowe

Dodaj kombinację klawiszy komendą notacji klawiszy lub skrótem klawiszowym Alt+K.

Reprezentuj kombinacje klawiszowe używając taga <kbd>. Oddziel od siebie klawisze znakiem plus, np <kbd>Alt+Tab</kbd>.

Indeks górny oraz dolny

Przykład: wpisując H2O i m2 otrzymasz: H₂O i m².

Składnia Tex

By precyzyjnie wyrazić działanie matematyczne, użyj składni Tex.

<tex>arcctg(x) = argtan(\frac{1}{x}) = arcsin(\frac{1}{\sqrt{1+x^2}})</tex>

Kod źródłowy

Krótkie fragmenty kodu

Wszelkie jednolinijkowe instrukcje języka programowania powinny być zawarte pomiędzy obróconymi apostrofami: `kod instrukcji` lub ``console.log(`string`);``.

Kod wielolinijkowy

Dodaj fragment kodu komendą . Fragmenty kodu zajmujące całą lub więcej linijek powinny być umieszczone w wielolinijkowym fragmencie kodu. Znaczniki ``` lub ~~~ umożliwiają kolorowanie różnych języków programowania. Możemy nadać nazwę języka programowania używając auto-uzupełnienia, kod został pokolorowany używając konkretnych ustawień kolorowania składni:

```javascript document.write('Hello World'); ```

Możesz zaznaczyć również już wklejony kod w edytorze, i użyć komendy by zamienić go w kod. Użyj kombinacji Ctrl+`, by dodać fragment kodu bez oznaczników języka.

Tabelki

Dodaj przykładową tabelkę używając komendy . Przykładowa tabelka składa się z dwóch kolumn, nagłówka i jednego wiersza.

Wygeneruj tabelkę na podstawie szablonu. Oddziel komórki separatorem ; lub |, a następnie zaznacz szablonu.

nazwisko;dziedzina;odkrycie
Pitagoras;mathematics;Pythagorean Theorem
Albert Einstein;physics;General Relativity
Marie Curie, Pierre Curie;chemistry;Radium, Polonium

Użyj komendy by zamienić zaznaczony szablon na tabelkę Markdown.

Lista uporządkowana i nieuporządkowana

Możliwe jest tworzenie listy numerowanych oraz wypunktowanych. Wystarczy, że pierwszym znakiem linii będzie * lub - dla listy nieuporządkowanej oraz 1. dla listy uporządkowanej.

Użyj komendy by dodać listę uporządkowaną.

1. Lista numerowana
2. Lista numerowana

Użyj komendy by dodać listę nieuporządkowaną.

* Lista wypunktowana
* Lista wypunktowana
** Lista wypunktowana (drugi poziom)

Składnia Markdown

Edytor obsługuje składnię Markdown, która składa się ze znaków specjalnych. Dostępne komendy, jak formatowanie , dodanie tabelki lub fragmentu kodu są w pewnym sensie świadome otaczającej jej składni, i postarają się unikać uszkodzenia jej.

Dla przykładu, używając tylko dostępnych komend, nie możemy dodać formatowania pogrubienia do kodu wielolinijkowego, albo dodać listy do tabelki - mogłoby to doprowadzić do uszkodzenia składni.

W pewnych odosobnionych przypadkach brak nowej linii przed elementami markdown również mógłby uszkodzić składnie, dlatego edytor dodaje brakujące nowe linie. Dla przykładu, dodanie formatowania pochylenia zaraz po tabelce, mogłoby zostać błędne zinterpretowane, więc edytor doda oddzielającą nową linię pomiędzy tabelką, a pochyleniem.

Skróty klawiszowe

Skróty formatujące, kiedy w edytorze znajduje się pojedynczy kursor, wstawiają sformatowany tekst przykładowy. Jeśli w edytorze znajduje się zaznaczenie (słowo, linijka, paragraf), wtedy zaznaczenie zostaje sformatowane.

Ctrl+B - dodaj pogrubienie lub pogrub zaznaczenie
Ctrl+I - dodaj pochylenie lub pochyl zaznaczenie
Ctrl+U - dodaj podkreślenie lub podkreśl zaznaczenie
Ctrl+S - dodaj przekreślenie lub przekreśl zaznaczenie

Notacja Klawiszy

Alt+K - dodaj notację klawiszy

Fragment kodu bez oznacznika

Alt+C - dodaj pusty fragment kodu

Skróty operujące na kodzie i linijkach:

Alt+L - zaznaczenie całej linii
Alt+, Alt+ - przeniesienie linijki w której znajduje się kursor w górę/dół.
Tab/⌘+] - dodaj wcięcie (wcięcie w prawo)
Shit+Tab/⌘+[ - usunięcie wcięcia (wycięcie w lewo)

Dodawanie postów:

Ctrl+Enter - dodaj post
⌘+Enter - dodaj post (MacOS)

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

Shalom

Shalom

sadasdzx

sadasdzx

asddasasdzxczxc

asddasasdzxczxc

endriuuu napisał(a):

sasasaas

Shalom

Smileys & People

Animals & Nature

Food & Drink

Travel & Places

Activities

Objects

Symbols

Typografia

Linki

Wewnętrzne odnośniki

Wspomnienia użytkowników

Znaczniki HTML

Skróty klawiszowe

Indeks górny oraz dolny

Składnia Tex

Kod źródłowy

Krótkie fragmenty kodu

Kod wielolinijkowy

Tabelki

Lista uporządkowana i nieuporządkowana

Składnia Markdown

Skróty klawiszowe