https://github.com/benmaier/binpacking
Distribution of weighted items to bins (either a fixed number of bins or a fixed number of volume per bin). Data may be in form of list, dictionary, list of tuples or csv-file.
Science Score: 26.0%
This score indicates how likely this project is to be science-related based on various indicators:
-
○CITATION.cff file
-
✓codemeta.json file
Found codemeta.json file -
✓.zenodo.json file
Found .zenodo.json file -
○DOI references
-
○Academic publication links
-
○Committers with academic emails
-
○Institutional organization owner
-
○JOSS paper metadata
-
○Scientific vocabulary similarity
Low similarity (10.2%) to scientific vocabulary
Repository
Distribution of weighted items to bins (either a fixed number of bins or a fixed number of volume per bin). Data may be in form of list, dictionary, list of tuples or csv-file.
Basic Info
Statistics
- Stars: 93
- Watchers: 2
- Forks: 16
- Open Issues: 4
- Releases: 6
Metadata Files
README.md
binpacking
This package contains greedy algorithms to solve two typical bin packing problems, (i) sorting items into a constant number of bins, (ii) sorting items into a low number of bins of constant size. Here's a usage example
```python
import binpacking
b = { 'a': 10, 'b': 10, 'c':11, 'd':1, 'e': 2,'f':7 } bins = binpacking.toconstantbin_number(b,4) # 4 being the number of bins print("===== dict\n",b,"\n",bins) ===== dict {'a': 10, 'b': 10, 'c': 11, 'd': 1, 'e': 2, 'f': 7} [{'c': 11}, {'b': 10}, {'a': 10}, {'f': 7, 'e': 2, 'd': 1}]
b = list(b.values()) bins = binpacking.toconstantvolume(b,11) # 11 being the bin volume print("===== list\n",b,"\n",bins) ===== list [10, 10, 11, 1, 2, 7] [[11], [10], [10], [7, 2, 1]] ```
Consider you have a list of items, each carrying a weight w_i. Typical questions are
- How can we distribute the items to a minimum number of bins N of equal volume V?
- How can we distribute the items to exactly N bins where each carries items that sum up to approximately equal weight?
Problems like this can easily occur in modern computing. Assume you have to run computations where a lot of files of different sizes have to be loaded into the memory. However, you only have a machine with 8GB of RAM. How should you bind the files such that you have to run your program a minimum amount of times? This is equivalent to solving problem 1.
What about problem 2? Say you have to run a large number of computations. For each of the jobs you know the time it will probably take to finish. However, you only have a CPU with 4 cores. How should you distribute the jobs to the 4 cores such that they will all finish at approximately the same time?
The package provides the command line tool "binpacking" using which one can easily bin pack csv-files containing a column that can be identified with a weight. To see the usage enter
$ binpacking -h
Usage: binpacking [options]
Options:
-h, --help show this help message and exit
-f FILEPATH, --filepath=FILEPATH
path to the csv-file to be bin-packed
-V V_MAX, --volume=V_MAX
maximum volume per bin (constant volume algorithm will
be used)
-N N_BIN, --n-bin=N_BIN
number of bins (constant bin number algorithm will be
used)
-c WEIGHT_COLUMN, --weight-column=WEIGHT_COLUMN
integer (or string) giving the column number (or
column name in header) where the weight is stored
-H, --has-header parse this option if there is a header in the csv-file
-d DELIM, --delimiter=DELIM
delimiter in the csv-file (use "tab" for tabs)
-q QUOTECHAR, --quotechar=QUOTECHAR
quotecharacter in the csv-file
-l LOWER_BOUND, --lower-bound=LOWER_BOUND
weights below this bound will not be considered
-u UPPER_BOUND, --upper-bound=UPPER_BOUND
weights exceeding this bound will not be considered
Install
$ pip install binpacking
Examples
In the repository's directory
cd examples/
binpacking -f hamlet_word_count.csv -V 2000 -H -c count -l 10 -u 1000
binpacking -f hamlet_word_count.csv -N 4 -H -c count
in Python
```python import binpacking
b = { 'a': 10, 'b': 10, 'c':11, 'd':1, 'e': 2,'f':7 } bins = binpacking.toconstantbin_number(b,4) print("===== dict\n",b,"\n",bins)
b = list(b.values()) bins = binpacking.toconstantvolume(b,11) print("===== list\n",b,"\n",bins)
```
Related packages
- prtpy by Erel Segal-Halevi.
- numberpartitioning by Søren Fuglede Jørgensen.
Owner
- Name: Benjamin F. Maier
- Login: benmaier
- Kind: user
- Location: Copenhagen
- Company: Technical University of Denmark
- Website: benmaier.org
- Twitter: benfmaier
- Repositories: 101
- Profile: https://github.com/benmaier
Postdoc @suneman 's, generative art, electronic music. DTU Compute & SODAS.
GitHub Events
Total
- Issues event: 2
- Watch event: 6
- Issue comment event: 4
- Push event: 1
- Pull request review event: 1
- Pull request event: 2
- Fork event: 2
Last Year
- Issues event: 2
- Watch event: 6
- Issue comment event: 4
- Push event: 1
- Pull request review event: 1
- Pull request event: 2
- Fork event: 2
Committers
Last synced: about 1 year ago
Top Committers
| Name | Commits | |
|---|---|---|
| Benjamin Maier | b****r@g****m | 36 |
| Rene Milk | r****k@w****e | 6 |
| Will Jones | w****s@m****m | 2 |
| owais09 | 5****9 | 1 |
| mprihoda | m****a@m****m | 1 |
| Markus Mohrhard | m****m@d****m | 1 |
| Ovidiu Munteanu | o****u@r****m | 1 |
Committer Domains (Top 20 + Academic)
Issues and Pull Requests
Last synced: 11 months ago
All Time
- Total issues: 26
- Total pull requests: 11
- Average time to close issues: 3 months
- Average time to close pull requests: 18 days
- Total issue authors: 23
- Total pull request authors: 8
- Average comments per issue: 3.04
- Average comments per pull request: 1.36
- Merged pull requests: 10
- Bot issues: 0
- Bot pull requests: 0
Past Year
- Issues: 1
- Pull requests: 1
- Average time to close issues: about 20 hours
- Average time to close pull requests: about 5 hours
- Issue authors: 1
- Pull request authors: 1
- Average comments per issue: 1.0
- Average comments per pull request: 3.0
- Merged pull requests: 1
- Bot issues: 0
- Bot pull requests: 0
Top Authors
Issue Authors
- pirovc (3)
- benmaier (2)
- SandorAlbert (1)
- mmohrhard (1)
- bsergean (1)
- erelsgl (1)
- romanRegmi (1)
- ka223 (1)
- ovidiu-munteanu (1)
- Prabin16 (1)
- Taarnborg (1)
- ghost (1)
- twjnorth (1)
- owais09 (1)
- bzamecnik (1)
Pull Request Authors
- benmaier (4)
- owais09 (2)
- ovidiu-munteanu (1)
- maprihoda (1)
- mmohrhard (1)
- R3tr0BoiDX (1)
- ghost (1)
- renefritze (1)
Top Labels
Issue Labels
Pull Request Labels
Packages
- Total packages: 2
-
Total downloads:
- pypi 77,027 last-month
- Total docker downloads: 3,053
-
Total dependent packages: 2
(may contain duplicates) -
Total dependent repositories: 18
(may contain duplicates) - Total versions: 17
- Total maintainers: 1
pypi.org: binpacking
Heuristic distribution of weighted items to bins (either a fixed number of bins or a fixed number of volume per bin). Data may be in form of list, dictionary, list of tuples or csv-file.
- Homepage: https://www.github.com/benmaier/binpacking
- Documentation: https://binpacking.readthedocs.io/
- License: MIT
-
Latest release: 1.5.2
published over 4 years ago
Rankings
Maintainers (1)
conda-forge.org: binpacking
- Homepage: https://www.github.com/benmaier/binpacking
- License: MIT
-
Latest release: 1.5.0
published about 5 years ago
Rankings
Dependencies
- future *