From: "Lukas Sandström" <lukass@etek.chalmers.se>
To: git@vger.kernel.org
Cc: "Lukas Sandström" <lukass@etek.chalmers.se>,
"Linus Torvalds" <torvalds@osdl.org>,
"Alex Riesen" <raa.lkml@gmail.com>,
junkio@cox.net
Subject: Re: fix git-pack-redundant crashing sometimes
Date: Thu, 17 Nov 2005 00:59:13 +0100 [thread overview]
Message-ID: <437BC7D1.1070605@etek.chalmers.se> (raw)
In-Reply-To: <437BA6A6.8080900@etek.chalmers.se>
Lukas Sandström wrote:
> Linus Torvalds wrote:
>
>>On Tue, 15 Nov 2005, Alex Riesen wrote:
>>
>>
>>>Sorry, it doesn't. The code loops here:
>>>
>>>401 /* find the permutations which contain all missing objects */
>>>402 perm_all = perm = get_all_permutations(non_unique);
>>
>>
>>Looks like the whole thing is exponential.
>>
>
> Slightly less, but not far from.
>
After doing some maths; actually it is very exponential. 2**n - 1 to be precise.
next prev parent reply other threads:[~2005-11-16 23:59 UTC|newest]
Thread overview: 25+ messages / expand[flat|nested] mbox.gz Atom feed top
2005-11-16 23:09 git-pack-redundant returns the most containing pack Alex Riesen
2005-11-16 23:23 ` Lukas Sandström
2005-11-15 15:49 ` fix git-pack-redundant crashing sometimes Alex Riesen
2005-11-15 16:08 ` Timo Hirvonen
2005-11-15 16:11 ` Alex Riesen
2005-11-15 17:28 ` Linus Torvalds
2005-11-15 21:38 ` Lukas Sandström
2005-11-15 21:24 ` [PATCH] Fix llist_sorted_difference_inplace in git-pack-redundant Lukas Sandström
2005-11-15 21:34 ` fix git-pack-redundant crashing sometimes Alex Riesen
2005-11-15 21:41 ` Lukas Sandström
2005-11-15 22:33 ` Alex Riesen
2005-11-15 23:13 ` Lukas Sandström
2005-11-16 7:01 ` Alex Riesen
2005-11-16 21:11 ` Alex Riesen
2005-11-15 23:58 ` Linus Torvalds
2005-11-16 20:13 ` Junio C Hamano
2005-11-16 21:37 ` Lukas Sandström
2005-11-16 23:59 ` Lukas Sandström [this message]
2005-11-17 16:56 ` Matthias Urlichs
2005-11-17 7:08 ` Fredrik Kuivinen
2005-11-17 13:11 ` [PATCH] Make git-pack-redundant non-horribly slow on large sets of packs Lukas Sandström
2005-11-17 20:39 ` Alex Riesen
2005-11-18 16:30 ` [PATCH] Fix bug introduced by the latest changes to git-pack-redundant Lukas Sandström
2005-11-18 21:53 ` [PATCH] Fix a bug in get_all_permutations Lukas Sandström
2005-11-17 7:45 ` git-pack-redundant returns the most containing pack Alex Riesen
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=437BC7D1.1070605@etek.chalmers.se \
--to=lukass@etek.chalmers.se \
--cc=git@vger.kernel.org \
--cc=junkio@cox.net \
--cc=raa.lkml@gmail.com \
--cc=torvalds@osdl.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).