SQL Server (και άλλες databases)

Re: Calculate prime numbers in SQL Server 2005

KelMan — Fri, 08 Jul 2005 18:58:00 GMT

Συμφωνώ απόλυτα, αυτό άλλωστε είπα κι εγώ αμέσως μετά το post του Γιώργου... Αλλά αφού σας είδα αποφασισμένους και αρχίσατε να δείχνετε κώδικα, είπα να προσθέσω κι εγώ τον οβολό μου ως προς το optimization...
Εξάλλου αυτό το performance hint εφαρμόζεται σε πολλές περιπτώσεις που οι developers έχουν συνηθίσει να χρησιμοποιούν temporary πίνακες...

Re: Calculate prime numbers in SQL Server 2005

Aris — Fri, 08 Jul 2005 18:48:32 GMT

Το πνεύμα των posts μου ήταν το ότι χρησιμοποιούμε το κατάλληλο εργαλείο για κάθε δουλειά (και, στην περίπτωσή μας, δεν "στραμπουλάμε" την T-SQL για να κάνουμε πράγματα για τα οποία δεν είναι φτιαγμένη..).

Στο post με το συννημένοt, θα βρείς ένα script (σε Perl) και το ισοδύναμο σε T-SQL. Η σύγκριση της απόδοσης (σαν τάξη μεγέθους) έχει την μεγαλύτερη σημασία, όχι οι πιθανές βελτιστοποιήσεις του κώδικα.

Άρης

Re: Calculate prime numbers in SQL Server 2005

KelMan — Fri, 08 Jul 2005 04:16:20 GMT

Μου φαίνεται περίεργος ο αλγόριθμος γιατί το κόσκινο δουλεύει ως εξής:
Γεμίζουμε έναν πίνακα Χ με τους αριθμούς 2 ως Ν (πχ 2 ως 100). Παίρνουμε τον πρώτο, τον ρίχνουμε σε ένα δεύτερο πίνακα Υ που θα περιέχει τους πρώτους και διαγράφουμε από τον Χ όλες τις τιμές όπου το υπόλοιπο της διαίρεσης με τον προηγούμενο αριθμό είναι 0. Συνεχίζουμε με τη σειρά όλους τους αριθμούς του Χ και σταματάμε όταν φτάσουμε στον αριθμό SQR(N). Τότε, ό,τι έχει μείνει μέσα στον X το ρίχνουμε στον Y. Πλεόν ο Y έχει όλους τους πρώτους αριθμούς από το 2 ως το Ν.
Γι αυτό είπα ότι δεν μου θυμίζει Κόσκινο του Ερατοσθένη, μιας και δεν είδα πουθενά τετραγωνική ρίζα...
Πάντως Άρη, νομίζω ότι το SP σου μπορεί να βελτιωθεί αν αντί για temporary πίνακα χρησιμοποιήσεις table variable...

Re: Calculate prime numbers in SQL Server 2005

Aris — Fri, 08 Jul 2005 02:51:09 GMT

Ήταν από το Algorithms in C++.

Πάντως, και αυτός που βρήκες δείχνει καλός . Πρέπει να ρωτήσουμε τον Ερατοσθένη...

Άρης

Re: Calculate prime numbers in SQL Server 2005

KelMan — Thu, 07 Jul 2005 16:16:21 GMT

Παίδες, νομίζω ότι ο αλγόριθμος για το κόσκινο του Ερατοσθένη πού έχετε γράψει παραπάνω δεν είναι σωστός... Εδώ θα βρείτε τον σωστό...

Re: Calculate prime numbers in SQL Server 2005

Aris — Thu, 07 Jul 2005 05:40:15 GMT

gcapnias wrote:

Αν το stored procedure ήταν στο SQL 2005 και σε μια .NET γλώσσα, θα ήταν άραγε πιο γρήγορο;

George J.

Θα το φροντίσω, το ΠΣΚ

Άρης

Re: Calculate prime numbers in SQL Server 2005

George J. Capnias — Thu, 07 Jul 2005 03:00:10 GMT

Αν το stored procedure ήταν στο SQL 2005 και σε μια .NET γλώσσα, θα ήταν άραγε πιο γρήγορο;

George J.

Re: Calculate prime numbers in SQL Server 2005

Aris — Thu, 07 Jul 2005 02:10:47 GMT

Σε (νέα) συνέχεια, το τυπικό κόσκινο του Ερατοσθένους είναι (σε sproc):
CREATE PROCEDURE sieve
@maxInt int
AS

-- fill temp table
create table #tmpPrimes (prime int primary key)

declare @num int
select @num=1
while (@num<=@maxInt)
BEGIN
insert into #tmpPrimes values (@num);
select @num = @num + 1
END

-- sieve
declare @i int, @j int
select @i = 2
while (@i <= @maxInt/2)
BEGIN
select @j = 2
while (@j <= @maxInt/@i)
BEGIN
update #tmpPrimes set prime = (-1) * prime where prime = @i * @j
select @j = @j + 1
END
select @i = @i + 1
END

insert into Primes1
select prime from #tmpPrimes where prime > 0
drop table #tmpPrimes
GO
όπου η παράμετρος είναι ο μέγιστος ακέραιος που θα εξετασθεί.

Χρειάζεται 6' 30" περίπου για να ψάξει μέχρι το 100k, δίνοντας περίπου 10k πρώτους.

Άρης

Re: Calculate prime numbers in SQL Server 2005

Aris — Wed, 06 Jul 2005 04:29:18 GMT

Σε συνέχεια των προηγουμένων, δεν νομίζω ότι η T-SQL είναι για τέτοιες δουλειές..

Εάν συγκρίνουμε ένα σκριπτάκι που να υπολογίζει πρώτους (σε Perl) και μία αντίστοιχης λογικής stored procedure (T-SQL, σε SQL2k) θα κλάψουμε...

Το σκριπτάκι υπολόγισε 25000 πρώτους σε 1' 31" και η stored procedure 5000 πρώτους σε 9' 21". Σημειωτέον ότι οι χρόνοι δεν είναι γραμμικοί (σαφές από τον αλγόριθμο).

Το συννημένο περιέχει ότι χρειάζεται για να πειραματιστείτε (εκτός από την Perl που θα βρείτε εδώ). Θα χρειαστεί να "σκαλίσετε" λίγο το script που φτιάχνει την βάση (ένας πίνακας και δύο sprocs - η μία είναι αυτή που σχολιάζω σε παραπάνω post)

Άρης

Re: Calculate prime numbers in SQL Server 2005

pontifikas — Tue, 05 Jul 2005 15:37:07 GMT

Με μια πρώτη ματιά, το 81 σίγουρα δεν είναι πρώτος...δεν ξέρω για άλλους.Είναι πολύ πρωί

Re: Calculate prime numbers in SQL Server 2005

Aris — Tue, 05 Jul 2005 04:56:23 GMT

Κρατώντας κάποιες επιφυλάξεις, έχω την αίσθηση ότι κάτι δεν πάει καλά...
Επιφυλάξεις:
1. Έκανα λάθη copy-paste
2. Οι αλλαγές στον κώδικα (χρήση μονίμου πίνακα για γράψιμο των πρώτων) τον αλλοίωσαν

Έτρεξα τον τροποποιημένο κώδικα που ακολουθεί σε SQL 2000 (PIV/3.0GHz, 1.5GB) και πήρε 17:50.593 να τρέξει (έγραφε...)
Ο κώδικας:
set nocount on
--declare @prime table (prime int not null primary key)
--insert into @prime values (2)
--insert into @prime values (3)
--insert into @prime values (5)
--insert into @prime values (7)
--insert into @prime values (11)
declare @number int, @pc int
set @number = 13
set @pc = 1
while @pc < 1000000
begin

   if not exists (select 1 from Primes1 where @number % prime = 0 and prime < sqrt(@number) )
   begin
      insert into Primes1 select @number
      set @pc = @pc +1
   end
   set @number = @number
            + case when @number %2 = 1 then 2
                   when @number %3 = 2 then 2
                   when @number %5 = 4 then 2
                   when @number %7 = 6 then 2
                   when @number %11 = 10 then 2
              else 1 end
   end
select @pc

Κληθηκε με το
use Primes

declare @start datetime
declare @end datetime

select @start = getdate()
exec dotNetZone1
select @end = getdate()

select @end-@start

όπου:
- Primes = το database
- dotNetZone1 = ο παραπάνω κώδικας σε sproc
- Primes1 = ο πίνακας που έγραφα (όμοιος με τον @prime του αρχικού κώδικα)

Τρέχοντας μετά ένα select top 100 prime from Primes1, πήρα τα εξής (μάλλον λανθασμένα) αποτελέσματα:
prime
-----------
13
15
17
19
21
23
25
27
29
31
33
35
37
39
41
43
45
47
49
51
53
55
57
59
61
63
65
67
69
71
73
75
77
79
81
83
85
87
89
91
93
95
97
99
101
103
105
107
109
111
113
115
117
119
121
123
125
127
129
131
133
135
137
139
141
143
145
147
149
151
153
155
157
159
161
163
165
167
169
171
173
175
177
179
181
183
185
187
189
191
193
197
199
201
203
205
207
209
211
213

(100 row(s) affected)

Μήπως κάτι δεν πάει καλά;

Άρης

Re: Calculate prime numbers in SQL Server 2005

KelMan — Mon, 04 Jul 2005 06:54:14 GMT

Σε T-SQL? Να φτιάξει κανείς κάτι καλύτερο από το κόσκινο του Ερατοσθένη; Χλωμό το βλέπω... Όποιος πάντως το κάνει, έχει σίγουρη θέση στην βιομηχανία της κρυπτογράφισης...

Calculate prime numbers in SQL Server 2005

George J. Capnias — Sun, 03 Jul 2005 08:25:58 GMT

Για να δούμε τι έχουμε εδώ...

Calculate prime numbers in SQL Server 2005

Thought I would start a challenge.

Who can come up with the best way of calculating prime numbers in SQL server. with all the progamability changes in 2005 there must be a really good way of doing it, or is there.

I've had a few stabs using a CTE and some TSQL put not that impressive, the CTE has limitations, the TSQL produced 1 million prime numbers in 7 minutes.

Can you do better

Heres the some code,

set nocount on
declare @prime table (prime int not null primary key)
--insert into @prime values (2)
--insert into @prime values (3)
--insert into @prime values (5)
--insert into @prime values (7)
--insert into @prime values (11)
declare @number int, @pc int
set @number = 13
set @pc = 1
while @pc < 1000000
begin

   if not exists (select 1 from @prime where @number % prime = 0 and prime < sqrt(@number) )
   begin
      insert into @prime select @number
      set @pc = @pc +1
   end
   set @number = @number
            + case when @number %2 = 1 then 2
                   when @number %3 = 2 then 2
                   when @number %5 = 4 then 2
                   when @number %7 = 6 then 2
                   when @number %11 = 10 then 2
              else 1 end
   end
select @pc

AND

with seq
as( select 13 number
union all
select s.number
+ case when s.number %2 = 1 then 2
when s.number %3 = 2 then 2
when s.number %5 = 4 then 2
when s.number %7 = 6 then 2
when s.number %11 = 10 then 2
else 1 end
from seq s
where number < 32767
)
, prime as (
select s.number
from seq s
where not exists ( select 1 from seq s2 where s2.number < s.number and (s.number) % s2.number = 0)
)
select *
from prime
option (MAXRECURSION 32767)

Original Link

Tuesday 23:18 | SimonSabin

Ποιος μπορεί να φτιάξει κάτι καλύτερο;

George J.