novaBBS - comp.lang.python - Re: memoization (original Subject lost because mailer lost the whole thread)

Re: memoization (original Subject lost because mailer lost the whole thread)

<mailman.469.1663608695.20444.python-list@python.org>

https://www.novabbs.com/devel/article-flat.php?id=19555&group=comp.lang.python#19555

copy link Newsgroups: comp.lang.python

Path: i2pn2.org!i2pn.org!aioe.org!news.mixmin.net!news2.arglkargh.de!news.karotte.org!fu-berlin.de!uni-berlin.de!not-for-mail
From: dvl...@psu.edu (Christman, Roger Graydon)
Newsgroups: comp.lang.python
Subject: Re: memoization (original Subject lost because mailer lost the whole
thread)
Date: Mon, 19 Sep 2022 17:31:31 +0000
Lines: 63
Message-ID: <mailman.469.1663608695.20444.python-list@python.org>
References: <MN2PR02MB68466E19F8D46DF826A8673DA84D9@MN2PR02MB6846.namprd02.prod.outlook.com>
Mime-Version: 1.0
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
X-Trace: news.uni-berlin.de RXcXFomdzV88Uul09PyWYAf2CdTgEk//yYmTq7os0wwg==
Return-Path: <dvl@psu.edu>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
Authentication-Results: mail.python.org; dkim=pass
reason="1024-bit key; unprotected key"
header.d=psu.edu header.i=@psu.edu header.b=me3BHWxv;
dkim-adsp=pass; dkim-atps=neutral
X-Spam-Status: OK 0.052
X-Spam-Evidence: '*H*': 0.90; '*S*': 0.00; '(which': 0.04; "python's":
0.05; '???': 0.07; 'allocation': 0.09; 'calculating': 0.09;
'numpy': 0.09; 'values.': 0.09; '>': 0.14; 'memory': 0.15;
'arguments': 0.16; 'caching': 0.16; 'call,': 0.16; 'easy,': 0.16;
'exponential': 0.16; 'fibonacci': 0.16; 'frequently': 0.16;
'functions,': 0.16; 'linear': 0.16; 'repeatedly.': 0.16;
'revising': 0.16; 'roger': 0.16; 'slow': 0.16; 'subject:thread':
0.16; 'times,': 0.16; 'python': 0.16; 'values': 0.17;
'applications': 0.17; 'instead': 0.17; 'uses': 0.19; 'calls':
0.19; 'to:addr:python-list': 0.20; "i've": 0.22; 'maybe': 0.22;
'purposes': 0.22; 'code': 0.23; 'run': 0.23; 'to:name:python-
list@python.org': 0.24; 'depends': 0.25; 'questions,': 0.26;
'seems': 0.26; 'months,': 0.26; 'function': 0.27; 'done': 0.28;
'expect': 0.28; 'default': 0.31; 'effect': 0.31; 'program': 0.31;
'but': 0.32; "i'll": 0.33; '100': 0.33; 'same': 0.34; 'one.':
0.35; 'respect': 0.35; 'runs': 0.35; 'close': 0.35; 'cases': 0.36;
'functions': 0.36; 'those': 0.36; 'using': 0.37; 'could': 0.38;
'enough': 0.39; 'table': 0.39; 'still': 0.40; 'define': 0.40;
'otherwise,': 0.40; 'both': 0.40; 'should': 0.40; 'reasonable':
0.62; 'come': 0.62; 'days': 0.62;
'received:namprd02.prod.outlook.com': 0.64; 'spend': 0.64;
'structure,': 0.64; 'your': 0.64; 'improve': 0.66; 'time.': 0.66;
'now,': 0.67; 'generally': 0.67; 'items': 0.68; 'cost': 0.69;
'-----': 0.69;
'received:nam12-bn8-obe.outbound.protection.outlook.com': 0.69;
'times': 0.69; 'took': 0.69; 'within': 0.69; '1000': 0.70; 'you.':
0.71; 'charset:iso-8859-1': 0.73; 'price': 0.75; '....': 0.76;
'fortunately,': 0.84; 'pennsylvania': 0.84; 'received:40.107.237':
0.84; 'savings,': 0.84; 'subject: \n ': 0.84; 'subject:original':
0.84; 'tables': 0.84; 'that...': 0.84; 'time).': 0.84; 'times"':
0.84; 'wins': 0.91; 'storage': 0.95
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none;
b=g4iMGt5GxJUjoXzkzURHKgg89fOr7N1KHRtX7eCMoOihVUGBBQvrwtC6+n/NbdphKPJkENQHLUjiZiBCLmmZ5lNoqjNac8iNjn5/tBotoni3de1Wq/9GfdSnX3ZZuZQc4Y63R6nXQ5iGHm9tCMmYVoCVtMI2M5GavFN7ssqUEepyaLjG0ApckUkQ+QDQ2+fmpxZwhbARhvIPumT3dEB0omjTN8zMQZs8jydlyai6W+sjFTkRZm9MUtW6mjUHimsgQJRAdhfyR7D+OSvTIri3Vxi3ihTfZoT3BmOdAwC5zqvTos+fcVWrtNq46jeRdPot/IZyPrVcXaVNufOzJkY4zQ==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com;
s=arcselector9901;
h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1;
bh=3a2Z9SxR8YAo1qjm5FQVDUbRwIxO2YVzDm5R3t3iK3E=;
b=EHxcPtLBTenURs6f5HQHueA8nnGQc47iqbzAP1FjWhFCD+Xs70WV9FrO16zpNtLkLhSkjCe0b7L6MMHkyWk/05d4PuuZOcPLzph7WkqMc6hWf26FlNi5mc9yGqpx0VkRxknbacmIzESbrTmZFzcYjaUvvWy93zie0R7g8eAvi4qfnWEcRhkD9hfRur8R1Bl3Ajv6IQeQx5jJnrtm2/Qy+TbV6kkSM8fqH9CClPcKX5t/i4oyY1QCpsDo0J/V0qFfxL71g6Ab6JwRDFwpalpmAC3Fdrc+7C9wpuoBtcy0cNrSRjVMnYTkS4aL5W29Wybna9IFvJLtLfgaX0jGhRl3ZQ==
ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass
smtp.mailfrom=psu.edu; dmarc=pass action=none header.from=psu.edu; dkim=pass
header.d=psu.edu; arc=none
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=psu.edu; s=selector1;
h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck;
bh=3a2Z9SxR8YAo1qjm5FQVDUbRwIxO2YVzDm5R3t3iK3E=;
b=me3BHWxvlejjWD4K7CgmIx7rJyJSMmO6sf2OC34YWW4TPrEPw7FwcJC20yUg0RHbK6wgMXw1BqMjX/yz0+DYwqiUxsHzd1uNWdnt4GGEp4SrHu449WjyZFi1Zr8Ha8rkGCVsEH/avWzsPod3178KFp8uV0NxSIHyNbIVs9XNu6M=
Thread-Topic: memoization (original Subject lost because mailer lost the whole
thread)
Thread-Index: AQHYzEo003li6M9p6E+n7WBBf88UIQ==
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
msip_labels:
authentication-results: dkim=none (message not signed)
header.d=none;dmarc=none action=none header.from=psu.edu;
x-ms-publictraffictype: Email
x-ms-traffictypediagnostic: MN2PR02MB6846:EE_|BL3PR02MB7969:EE_
x-ms-office365-filtering-correlation-id: 0075bab0-8fb2-41c5-d2a7-08da9a64cae8
x-ms-exchange-senderadcheck: 1
x-ms-exchange-antispam-relay: 0
x-microsoft-antispam: BCL:0;
x-microsoft-antispam-message-info: mGocSTzYKSJMD+ZMyg8c6hxkef/7Ij1XdghLgn574cMnwMaJQ2lbs60KlwAL2dyNZ4iDnAw7Q9CBBPh/9qebsUlh2hwRIzUrSqZc5gP2jrLod9+B25kubi1k8SipiqoEEceTqBn0Pz67BzS5UorUtcguyRfkEsTYvZ2SJrByTZ7HiqvgONzpKERcjiZim3ujai93MZYfI3rmyX8N7Fj9Nr4YDyhtPEA7qJTbmcp7vdgUpSKmnZjmBPLCu4yRia0uAyeBg+iny+xDnz6sZCCjx7W2HhSzEWYJCRg3uMbgUOIYXv1MJty2paPCPiz45yILdathW5QS6mVhJ+Yf8bQXFhyNGbLHCsDhVMJHMBbh8xUxMz0zjHQSWCfivlldMVM/X9fHWq+VIsbe8daM7/zprDIds+Q3Czdhll8+NqRZdgtw2Lze4WjRDcMjTObaRl/HqS+VfGypuXUtOWf8xoYtlXq437OJ1BaueIKLe/8rNAyUVSxNhUmO95N5evdI4A5VTe37BURMjohe0NGPV/bpQBy4el2tdoGy8ahHn+U9QDJMRYtYfPxXkLZRwhmM7/Ph8w1wgqbSgy7wh6qP5C+ptGEKg65VqS/+78Zaf9lAH6LPKOl+Ob6KBq0l6gSSgQoPobp+ejqykSNPksDSJMVEeFFoK2kRRxWW9z/iN3R7omeEXVB7CqTdBNoU9AYtRyrFL8lGrwwgmRq0JCiU93DVi4+XJ0vv/JBwcoyjesxSfm1IUY13HYFdwL8+WY5JFIhFJyW0h2Jqne1b5Oqy0zJbIg==
x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:;
IPV:NLI; SFV:NSPM; H:MN2PR02MB6846.namprd02.prod.outlook.com; PTR:; CAT:NONE;
SFS:(13230022)(4636009)(39860400002)(366004)(136003)(396003)(346002)(376002)(451199015)(2906002)(7696005)(38070700005)(41300700001)(6506007)(55016003)(33656002)(76116006)(8676002)(66556008)(75432002)(83380400001)(6916009)(64756008)(66476007)(66946007)(316002)(786003)(66446008)(71200400001)(52536014)(5660300002)(86362001)(186003)(8936002)(478600001)(26005)(38100700002)(9686003)(19627405001)(122000001);
DIR:OUT; SFP:1102;
x-ms-exchange-antispam-messagedata-chunkcount: 1
x-ms-exchange-antispam-messagedata-0: lpaxAZUzG3BHiEHUfOUuMqiYtXM8Bp27kO/Qzh9PVamlETJIyACASAsfgY
dgajnwVuRNtVZEXMQ2taNUQSnymhZ9RkduheRFPQ5JM3NTc1Mnq6QyrxYr
D6uplrDDlmakbAivjaxKj/FVMRzfwz9G0hlZKZsVocHxXAFweicf4tiwUp
WBKA+IzSTl/AUeE/r4i9+Du6GVT3WFBUVf71p+GKDc/Psasyx86C523y8j
YrqG7wbG9XIzwLe69vFAOrSWPTM7age4FfM/NWpQ4BwN3v0OvQJvy+RdQB
KFjjTm47+mAP9PWU42FJaci6TVmUdx/ENz94Lq2xENoSuwJ9hq8LmcPJZ/
iKIXT1zElFfC+haDZsh4CL3nqc4lnYHjUm9cFcaWsJUJK1p8tUOjm1X+E2
D6+hb1sfApRrHT0SsjU7/9rfE9/eXM3lU4XTOGd2X9fOWe+Q+RfQ0uNmcq
s0lpF+O7cr3hi5MDhy4cYMdlbwhqsOKz7fF5gUUIHCPxZ/B8AS5+Ck2E0L
BmwX3ZGAZxJuKwupEgG5AsPsGxyBMlRE8jiGXD7l81h+qWNDN3fK1ry7n2
JC/G+i/UkrlEAciSkgrqz7TrXiHk4F3ygeLNNP0wA+RYOx4jYEe/4iB9sM
Q+AlZjDGKXLKcZh0brfsEr26n0Hc9AocUu2BOV/LDyKTe+4xeq3nVfRL9D
VBt76wpWunEJI2OibOwpNE83Ee7wIYcLYA24Lx1ruVMefLQU5v4luavrNN
iaS8S4u2kDf2L+UadAVvIlY3VbvqGJc9LBkAH8c5HyYbTW8hKUezWK7c08
LgyOE1JmUaWc/28NHC8OqWA13xMKQ1u0NPUibGkV9zoqvH7P24W9Ii0L9v
WQnmOoxFirMxHgM+WtRh6muOa4mIZaL9O4gn1BO60XEe02prneT7TXCdPv
LYXeWq3YXb2AYEPv/y47IOxmbHFY0Wv+qxujdQRdZfiSRjnB9byWQzS6Ji
cWaRhZgnCZKuMsY/suvJ1FwafDYu4MwI/h4yueNQ15Yba1NL/0XmdIzYgq
1RdiGKCBaOq6HuWtWymv58sV50jOUpHC3p4Wj5TMqtoBv3QgFs4jMsoN30
kG1pO6V+S3utBjQdcLikOxUrm4qKzUXBeLEcjrpUYyIIG8MFgd7ni2iJyo
Mn4uFhAsgQjYmK6YqWARaLFIHSNYdWYOvt0/AkSGlG0nFBG78yV2u1zLw7
X5sG9Q1Y0DVFEDGaZKN0Xp9tksTOkDXqVXVELfRXCYvCY0fDZk0s7W0TdK
yzds2fqbrTgf0l93KgrKVupUUhomOY5J/ZWvGmgkIrQiIF+L255xvemOkj
zoJpiw4JOhvuotEDJcppWVfmk0P2edw2hXci6pVWNCk3HjEVaHVnMCee+m
ODzGZRAfpRPcOjwXP8P4LdCQ8WM2P4W+9t1m3fsOCj93s6TNxen5rGWBpN
TUL4JLIPwa1q1uFV/gVzaSFnXYdMZiCL3EJCwim6xbL7uuCSknWat96/A8
/IhrqcUw0d3daGTrpEu2I4/5cFdBoGIIab1JT1c+dQCR46wZCw==
X-OriginatorOrg: psu.edu
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-AuthSource: MN2PR02MB6846.namprd02.prod.outlook.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 0075bab0-8fb2-41c5-d2a7-08da9a64cae8
X-MS-Exchange-CrossTenant-originalarrivaltime: 19 Sep 2022 17:31:31.7384 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 7cf48d45-3ddb-4389-a9c1-c115526eb52e
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-CrossTenant-userprincipalname: zdRSE5lku1tGUnYZuelWNhhEuZLTUcww5rTuuDh7t8kBS6UqnsJsDBcwT8xckaFN
X-MS-Exchange-Transport-CrossTenantHeadersStamped: BL3PR02MB7969
X-Content-Filtered-By: Mailman/MimeDel 2.1.39
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.39
Precedence: list
List-Id: General discussion list for the Python programming language
<python-list.python.org>
List-Unsubscribe: <https://mail.python.org/mailman/options/python-list>,
<mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <https://mail.python.org/pipermail/python-list/>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <https://mail.python.org/mailman/listinfo/python-list>,
<mailto:python-list-request@python.org?subject=subscribe>
X-Mailman-Original-Message-ID: <MN2PR02MB68466E19F8D46DF826A8673DA84D9@MN2PR02MB6846.namprd02.prod.outlook.com>

by: Christman, Roger Gra - Mon, 19 Sep 2022 17:31 UTC

"Hen Hanna" <henhanna@gmail.com> asked:
> so... for a few days i've been revising this Code (in Gauche / Lisp / Scheme) to make it run faster.. and last night i could improve it enough to give me the result i wanted in 72 minutes or so (on my slow PC at home).

> ( Maybe... within a few months, i'll write the same program in Python ..... to see if it runs 10 or 20 times faster. )

> this was the first time i've used Caching (memoization). ----- instead of calculating (at run-time) Factorial(x) and Combination(x,y) millions of times, i made 2 tables in advance... A simple Table-lookup (Vector-ref in Scheme) seems 100 -- 1000 times faster.

> One thought i had was... Maybe Python's Factorial(x) and Combination(x,y) (in Numpy ?) are already so fast that... i don't have to do the Caching (memoization) ???

Memoization will generally be very fast -- since it is essentially a table-lookup. If it uses a hash-table (which is common for dictionaries), it would be close to a constant-time access for any entry; otherwise, if it uses some tree structure, it might be logarithmic in the number of entries in the tree.

But that fast access comes at a price of storage -- linear with respect to the number of items stored (versus no memory cost incurred when not memoizing).

What effect this has when you call these functions "millions of times" depends very much one how many of those calls are on the same values. If all of the calls have different arguments, memoization would not find it in the table yet, and would have to recompute as normal -- and you would end up with no time savings, but a considerable memory allocation for all of those newly-cached values that you never retrieve. The big wins come from asking the same questions repeatedly.

Now, as far as Python's functionality, I would not expect it to do any memoization for you. It certainly could not predict what arguments would provide, but it still could still have a reasonable implementation without memoization. Your Factorial(x) and Combination(x,y) would both require a time linear with respect to the value of x, with no memory cost incurred.

But if you were to spend most of your application asking the same questions, I would not expect these functions to do any caching or memoization, since I would expect very few applications would have enough calls to these functions to make it worthwhile. So calling these functions, you can expect a linear time for each function call, and if you expect to frequently repeat arguments, then you should add your own memoization for an amortized linear time.

And fortunately, Python makes memoization very easy, by using a dictionary as a default value. I've done that often for classroom purposes for cases where it makes a big difference (recursive Fibonacci accelerates from exponential time to linear time). And the process is straightforward enough that you could even define a decorator that could be applied to any function you choose. I don't have an example handy just because I never took the time to write one.

Roger Christman
Pennsylvania State University

Subject	Author
Re: memoization (original Subject lost because mailer lost the whole	Christman, Roger Graydon

One can't proceed from the informal to the formal by formal means.

devel / comp.lang.python / Re: memoization (original Subject lost because mailer lost the whole thread)