Re: [HACKERS] Issues with factorial operator
Hi, 2007/6/9, Dann Corbit [EMAIL PROTECTED]: It makes sense with factorial function to do an error check on the domain. Calculate beforehand, and figure out what the largest sensible domain value is. well, in fact what we need is to calculate log10(n!) first to see if the result will get exceeded. For instance, in Maple, I get this: y:=92838278!; Error, object too large The error message returns instantly. For reasonably large values, it might make sense to pre-compute factorials and store them in an array. It should also be possible to store 1/2 of Pascal's triangle in memory and demand load that memory segment the first time someone asks for factorials or combinations or permutations. there may be too much memories to waste in that case... :-( Regards CUI Shijun ---(end of broadcast)--- TIP 4: Have you searched our list archives? http://archives.postgresql.org
Re: [HACKERS] Issues with factorial operator
2007/6/9, Dann Corbit [EMAIL PROTECTED]:
#include math.h
double log10nfactorialestimate(unsigned n)
{
unsignedi;
double estimate = 0;
for (i = 1; i n; i++)
estimate += log10(n);
return estimate;
}
#ifdef UNIT_TEST
#include stdio.h
#include time.h
int main(void)
{
clock_t start,
end;
double answer;
start = clock();
end = clock();
answer = log10nfactorialestimate(92838278);
printf(log 10 of 92838278! is pretty close to %g and took %g
seconds\n,
answer, (end - start) / (1.0 * CLOCKS_PER_SEC));
return 0;
}
#endif
/*
C:\tmpcl /W4 /Ox /DUNIT_TEST log10EST.C
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 14.00.50727.42
for 80x86
Copyright (C) Microsoft Corporation. All rights reserved.
log10EST.C
Microsoft (R) Incremental Linker Version 8.00.50727.42
Copyright (C) Microsoft Corporation. All rights reserved.
/out:log10EST.exe
log10EST.obj
C:\tmplog10est
log 10 of 92838278! is pretty close to 7.3971e+008 and took 0 seconds
*/
Hum... I think there is a little improvement: when n is too large,(say
n10, 000) we can use Stirling's formula to get the estimated value of
n!:-)
---(end of broadcast)---
TIP 4: Have you searched our list archives?
http://archives.postgresql.org
Re: [HACKERS] Issues with factorial operator
yeah, simple and correct, I like that. :-)
2007/6/9, Dann Corbit [EMAIL PROTECTED]:
-Original Message-
[snip]
Hum... I think there is a little improvement: when n is too large,(say
n10, 000) we can use Stirling's formula to get the estimated value of
n!:-)
Or (rather) the log base 10 of Stirling's formula. The n! estimator
will overflow for sure, unless we take the log of it.
Rather than all that, why not just figure out what the largest number of
digits we will allow is and then don't allow inputs that will generate
more than that.
The program I gave could be run with the target accuracy as the break
out of the loop and then the test would be:
type factorial(type n)
{
if (n CONSTANT_PRECOMPUTED_LIMIT)
return NULL;
else
{
return compute_actual_factorial(n);
}
}
---(end of broadcast)---
TIP 4: Have you searched our list archives?
http://archives.postgresql.org
Re: [HACKERS] Lack of urgency in 8.3 reviewing
I want to help the reviewing work of ctid chain following enhancement . I've been studying the souce code which related with that part recently. :-) 2007/5/17, Dave Page [EMAIL PROTECTED]: I think we just have to accept that we're gonna have a long feature freeze period, and ask people to help review whatever they can. Regards, Dave. ---(end of broadcast)--- TIP 6: explain analyze is your friend ---(end of broadcast)--- TIP 7: You can help support the PostgreSQL project by donating at http://www.postgresql.org/about/donate
Re: [HACKERS] Lack of urgency in 8.3 reviewing
I see... I checked part of HOT patches(patch1), and found that it involves too many things I am not currently familar with. Maybe I should change an item to work. :-( Since I only studied part of source codes about transaction processing(lmgr/MVCC/xact but without xlog.c), I want to study Group Commit patch and try to review it, any suggestions? 2007/5/17, Bruce Momjian [EMAIL PROTECTED]: Pavan Deolasee wrote: On 5/17/07, Cui Shijun [EMAIL PROTECTED] wrote: I want to help the reviewing work of ctid chain following enhancement . I've been studying the souce code which related with that part recently. :-) Tom had objected to this patch on the grounds that it adds complexity without any significant gains. Though I don't completely agree with the first part, the second part is indeed debatable since the code is touched only for infrequently. Right. The reason the patch was kept in the queue is that there was discussion that HOT will exercise that part of the code a lot more than it does currently. -- Bruce Momjian [EMAIL PROTECTED] http://momjian.us EnterpriseDB http://www.enterprisedb.com + If your life is a hard drive, Christ can be your backup. + ---(end of broadcast)--- TIP 6: explain analyze is your friend
Re: [HACKERS] Lack of urgency in 8.3 reviewing
Thank you for your suggestions, I am thinking about Full page writes improvement. It seems not so complicated, just fit for a novice like me. I'll work on it. :-) 2007/5/17, Heikki Linnakangas [EMAIL PROTECTED]: Cui Shijun wrote: I see... I checked part of HOT patches(patch1), and found that it involves too many things I am not currently familar with. Maybe I should change an item to work. :-( Yeah, that's one big patch.. Since I only studied part of source codes about transaction processing(lmgr/MVCC/xact but without xlog.c), I want to study Group Commit patch and try to review it, any suggestions? There's no group commit patch, just some discussion, and probably won't be until 8.4. Maybe one of these would interest you: - deferred transaction/waitless COMMIT - full page writes improvement - maintaining cluster order on insert - heap page diagnostic functions Make sure you look at the latest version of the patches. -- Heikki Linnakangas EnterpriseDB http://www.enterprisedb.com ---(end of broadcast)--- TIP 4: Have you searched our list archives? http://archives.postgresql.org
Re: Fwd: [HACKERS] How does the partitioned lock manager works?
Ah... It seems that a item is calculated its hash value, get the bucket number from it and insert into that bucket chain. The insertion has nothing to do with partition number(but Alvaro says which hash is used depends on the partition number. I haven't really understood this: how can we get a hash value without deciding which hash to use? ). However, when we travel along a chain to get a item, we can infer its partition number from its hash value. My problem is, I'm not so sure about the process stated above, because in that way, items in ONE chain may belong to different partitions,and it is obviously conflicted with so that different partitions use different hash chains as README mentioned. 2007/4/28, Tom Lane [EMAIL PROTECTED]: It's not that hard: the bucket number is some number of low-order bits of the hash value, and the partition number is some smaller (or at most equal) number of low-order bits of the hash value. regards, tom lane
Re: Fwd: [HACKERS] How does the partitioned lock manager works?
2007/4/28, Heikki Linnakangas [EMAIL PROTECTED]: 3. Lock that partition 6. Unlock partition I suddenly realize that LW locks are used to manage the lock hash table.So when a item is to be inserted into hash table, we must gain that partition lock first to change that table. As the insertion algorithm described, a specific partition lock manage some items, but these items can be stored in anywhere of the hash table,not necessarily in a bucket chain. So there are some problems with different partitions use different hash chains, a partition can use different hash chains,too. Am I right?
