Skip to content

Instantly share code, notes, and snippets.

@antimon2

antimon2/20230220CntLenIncDecSub.by.Sb2.ipynb

Last active February 22, 2023 04:00
Show Gist options
  • Save antimon2/9920d64269220d92faf27e207ec73f6f to your computer and use it in GitHub Desktop.
Save antimon2/9920d64269220d92faf27e207ec73f6f to your computer and use it in GitHub Desktop.
Download ZIP
20230220CntLenIncDecSub.by.Sb2.ipynb
Display the source blob
Display the rendered blob
Raw
20230220CntLenIncDecSub.by.Sb2.ipynb
{
"cells": [
{
"metadata": {
"ExecuteTime": {
"start_time": "2023-02-22T01:46:03.881Z",
"end_time": "2023-02-22T10:46:03.545000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "versioninfo()",
"execution_count": 1,
"outputs": [
{
"output_type": "stream",
"text": "Julia Version 1.8.5\nCommit 17cfb8e65ea (2023-01-08 06:45 UTC)\nPlatform Info:\n OS: Linux (x86_64-linux-gnu)\n CPU: 12 × Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz\n WORD_SIZE: 64\n LIBM: libopenlibm\n LLVM: libLLVM-13.0.1 (ORCJIT, skylake)\n Threads: 4 on 12 virtual cores\nEnvironment:\n JULIA_NUM_THREADS = 4\n",
"name": "stdout"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2023-02-22T01:46:03.884Z",
"end_time": "2023-02-22T10:46:03.590000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "using Combinatorics",
"execution_count": 2,
"outputs": []
},
{
"metadata": {},
"cell_type": "markdown",
"source": "ref: https://github.com/tsatie/SatieGitHubTest/blob/master/20230220CntLenIncDecSub.ipynb (https://twitter.com/tsatie/status/1628040325406277634)"
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2023-02-22T01:46:03.887Z",
"end_time": "2023-02-22T10:46:03.917000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "function incdecSubseqCnt_rev1(ary)\n incpairs=[[ary[1],1]]\n decpairs=[[ary[1],1]]\n for i=2:length(ary)\n maxl,addj=1,-1\n for j=1:length(incpairs)\n if ary[i]>incpairs[j][1] && incpairs[j][2]>maxl-1\n addj,maxl=j,incpairs[j][2]+1\n end\n end\n if addj>0\n push!(incpairs,[ary[i],maxl])\n else\n push!(incpairs,[ary[i],1])\n end\n maxl,addj=1,-1\n for j=1:length(decpairs)\n if ary[i]<decpairs[j][1] && decpairs[j][2]>maxl-1\n addj,maxl=j,decpairs[j][2]+1\n end\n end\n if addj>0\n push!(decpairs,[ary[i],maxl])\n else\n push!(decpairs,[ary[i],1])\n end \n end\n incmaxl=1\n for i=1:length(incpairs) \n if incmaxl<incpairs[i][2]\n incmaxl=incpairs[i][2]\n end\n end\n decmaxl=1\n for i=1:length(decpairs) \n if decmaxl<decpairs[i][2]\n decmaxl=decpairs[i][2]\n end\n end\n return max(incmaxl,decmaxl)\nend",
"execution_count": 3,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 3,
"data": {
"text/plain": "incdecSubseqCnt_rev1 (generic function with 1 method)"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2023-02-22T01:46:03.889Z",
"end_time": "2023-02-22T10:46:14.115000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "@time for n = 3:10\n seq = Vector(1:n)\n p = union(permutations(seq))\n cntlst=zeros(Int32, n) \n for i = 1:length(p)\n j=incdecSubseqCnt_rev1(p[i])\n cntlst[j]=cntlst[j]+1\n end\n println(n,\" : \",cntlst)\nend",
"execution_count": 4,
"outputs": [
{
"output_type": "stream",
"text": "3 : Int32[0, 4, 2]\n4 : Int32[0, 4, 18, 2]\n5 : Int32[0, 0, 86, 32, 2]\n6 : Int32[0, 0, 306, 362, 50, 2]\n7 : Int32[0, 0, 882, 3242, 842, 72, 2]\n8 : Int32[0, 0, 1764, 24564, 12210, 1682, 98, 2]\n9 : Int32[0, 0, 1764, 163872, 161158, 32930, 3026, 128, 2]\n10 : Int32[0, 0, 0, 985032, 1969348, 592652, 76562, 5042, 162, 2]\n 9.997581 seconds (116.27 M allocations: 10.928 GiB, 22.39% gc time, 0.75% compilation time)\n",
"name": "stdout"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2023-02-22T01:46:03.891Z",
"end_time": "2023-02-22T10:46:21.112000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "@time for n = 3:10\n seq = 1:n\n ps = permutations(seq)\n cntlst=zeros(Int, n) \n for p = ps\n j = incdecSubseqCnt_rev1(p)\n cntlst[j] += 1\n end\n println(n,\" : \",cntlst)\nend",
"execution_count": 5,
"outputs": [
{
"output_type": "stream",
"text": "3 : [0, 4, 2]\n4 : [0, 4, 18, 2]\n5 : [0, 0, 86, 32, 2]\n6 : [0, 0, 306, 362, 50, 2]\n7 : [0, 0, 882, 3242, 842, 72, 2]\n8 : [0, 0, 1764, 24564, 12210, 1682, 98, 2]\n9 : [0, 0, 1764, 163872, 161158, 32930, 3026, 128, 2]\n10 : [0, 0, 0, 985032, 1969348, 592652, 76562, 5042, 162, 2]\n 6.912153 seconds (116.26 M allocations: 10.729 GiB, 15.80% gc time, 1.61% compilation time)\n",
"name": "stdout"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2023-02-22T01:46:03.893Z",
"end_time": "2023-02-22T10:46:21.116000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "using BenchmarkTools",
"execution_count": 6,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2023-02-22T01:46:03.895Z",
"end_time": "2023-02-22T10:46:21.116000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "using Random",
"execution_count": 7,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2023-02-22T01:46:03.896Z",
"end_time": "2023-02-22T10:46:25.690000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "Random.seed!(1234)\n@benchmark incdecSubseqCnt_rev1(p) setup=(p=Random.shuffle(1:10))",
"execution_count": 8,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 8,
"data": {
"text/plain": "BenchmarkTools.Trial: 10000 samples with 133 evaluations.\n Range \u001b[90m(\u001b[39m\u001b[36m\u001b[1mmin\u001b[22m\u001b[39m … \u001b[35mmax\u001b[39m\u001b[90m): \u001b[39m\u001b[36m\u001b[1m717.729 ns\u001b[22m\u001b[39m … \u001b[35m18.971 μs\u001b[39m \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmin … max\u001b[90m): \u001b[39m 0.00% … 94.49%\n Time \u001b[90m(\u001b[39m\u001b[34m\u001b[1mmedian\u001b[22m\u001b[39m\u001b[90m): \u001b[39m\u001b[34m\u001b[1m762.169 ns \u001b[22m\u001b[39m\u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmedian\u001b[90m): \u001b[39m 0.00%\n Time \u001b[90m(\u001b[39m\u001b[32m\u001b[1mmean\u001b[22m\u001b[39m ± \u001b[32mσ\u001b[39m\u001b[90m): \u001b[39m\u001b[32m\u001b[1m874.546 ns\u001b[22m\u001b[39m ± \u001b[32m 1.115 μs\u001b[39m \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmean ± σ\u001b[90m): \u001b[39m10.78% ± 7.97%\n\n \u001b[39m \u001b[39m▃\u001b[39m█\u001b[34m▆\u001b[39m\u001b[39m▃\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[32m \u001b[39m\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \n \u001b[39m▃\u001b[39m█\u001b[39m█\u001b[34m█\u001b[39m\u001b[39m█\u001b[39m█\u001b[39m▅\u001b[39m▃\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[32m▂\u001b[39m\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▁\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▁\u001b[39m▂\u001b[39m▂\u001b[39m \u001b[39m▃\n 718 ns\u001b[90m Histogram: frequency by time\u001b[39m 1.5 μs \u001b[0m\u001b[1m<\u001b[22m\n\n Memory estimate\u001b[90m: \u001b[39m\u001b[33m2.50 KiB\u001b[39m, allocs estimate\u001b[90m: \u001b[39m\u001b[33m26\u001b[39m."
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2023-02-22T01:46:03.897Z",
"end_time": "2023-02-22T10:46:25.766000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "function incdecSubseqCnt_rev2(ary)\n incpairs = [(ary[begin], 1)]\n decpairs = [(ary[begin], 1)]\n for a in ary[begin+1:end]\n maxl = 1\n addj = -1\n for (j, (b, len)) in pairs(incpairs)\n if a > b && len > maxl - 1\n addj = j\n maxl = len + 1\n end\n end\n if addj > 0\n push!(incpairs, (a, maxl))\n else\n push!(incpairs, (a, 1))\n end\n maxl = 1\n addj = -1\n for (j, (b, len)) in pairs(decpairs)\n if a < b && len > maxl - 1\n addj = j\n maxl = len + 1\n end\n end\n if addj > 0\n push!(decpairs, (a, maxl))\n else\n push!(decpairs, (a, 1))\n end \n end\n incmaxl = maximum(len for (_a, len) in incpairs)\n decmaxl = maximum(len for (_a, len) in decpairs)\n return max(incmaxl, decmaxl)\nend",
"execution_count": 9,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 9,
"data": {
"text/plain": "incdecSubseqCnt_rev2 (generic function with 1 method)"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2023-02-22T01:46:03.898Z",
"end_time": "2023-02-22T10:46:30.479000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "@time for n = 3:10\n seq = 1:n\n ps = permutations(seq)\n cntlst=zeros(Int, n) \n for p = ps\n j = incdecSubseqCnt_rev2(p)\n cntlst[j] += 1\n end\n println(n,\" : \",cntlst)\nend",
"execution_count": 10,
"outputs": [
{
"output_type": "stream",
"text": "3 : [0, 4, 2]\n4 : [0, 4, 18, 2]\n5 : [0, 0, 86, 32, 2]\n6 : [0, 0, 306, 362, 50, 2]\n7 : [0, 0, 882, 3242, 842, 72, 2]\n8 : [0, 0, 1764, 24564, 12210, 1682, 98, 2]\n9 : [0, 0, 1764, 163872, 161158, 32930, 3026, 128, 2]\n10 : [0, 0, 0, 985032, 1969348, 592652, 76562, 5042, 162, 2]\n 4.629866 seconds (40.29 M allocations: 8.353 GiB, 20.87% gc time)\n",
"name": "stdout"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2023-02-22T01:46:03.899Z",
"end_time": "2023-02-22T10:46:32.093000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "Random.seed!(1234)\n@benchmark incdecSubseqCnt_rev2(p) setup=(p=Random.shuffle(1:10))",
"execution_count": 11,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 11,
"data": {
"text/plain": "BenchmarkTools.Trial: 10000 samples with 240 evaluations.\n Range \u001b[90m(\u001b[39m\u001b[36m\u001b[1mmin\u001b[22m\u001b[39m … \u001b[35mmax\u001b[39m\u001b[90m): \u001b[39m\u001b[36m\u001b[1m311.767 ns\u001b[22m\u001b[39m … \u001b[35m 4.454 μs\u001b[39m \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmin … max\u001b[90m): \u001b[39m0.00% … 86.33%\n Time \u001b[90m(\u001b[39m\u001b[34m\u001b[1mmedian\u001b[22m\u001b[39m\u001b[90m): \u001b[39m\u001b[34m\u001b[1m327.150 ns \u001b[22m\u001b[39m\u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmedian\u001b[90m): \u001b[39m0.00%\n Time \u001b[90m(\u001b[39m\u001b[32m\u001b[1mmean\u001b[22m\u001b[39m ± \u001b[32mσ\u001b[39m\u001b[90m): \u001b[39m\u001b[32m\u001b[1m366.165 ns\u001b[22m\u001b[39m ± \u001b[32m289.247 ns\u001b[39m \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmean ± σ\u001b[90m): \u001b[39m7.64% ± 8.77%\n\n \u001b[39m█\u001b[34m▇\u001b[39m\u001b[39m \u001b[32m \u001b[39m\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m▁\n \u001b[39m█\u001b[34m█\u001b[39m\u001b[39m█\u001b[32m▇\u001b[39m\u001b[39m█\u001b[39m█\u001b[39m▇\u001b[39m▇\u001b[39m▇\u001b[39m█\u001b[39m█\u001b[39m▆\u001b[39m▇\u001b[39m▆\u001b[39m▅\u001b[39m▆\u001b[39m▆\u001b[39m▆\u001b[39m▅\u001b[39m▅\u001b[39m▄\u001b[39m▅\u001b[39m▅\u001b[39m▅\u001b[39m▄\u001b[39m▁\u001b[39m▁\u001b[39m▄\u001b[39m▆\u001b[39m█\u001b[39m█\u001b[39m▆\u001b[39m▄\u001b[39m▃\u001b[39m▃\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▃\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▃\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▃\u001b[39m \u001b[39m█\n 312 ns\u001b[90m \u001b[39m\u001b[90mHistogram: \u001b[39m\u001b[90m\u001b[1mlog(\u001b[22m\u001b[39m\u001b[90mfrequency\u001b[39m\u001b[90m\u001b[1m)\u001b[22m\u001b[39m\u001b[90m by time\u001b[39m 1.34 μs \u001b[0m\u001b[1m<\u001b[22m\n\n Memory estimate\u001b[90m: \u001b[39m\u001b[33m1.88 KiB\u001b[39m, allocs estimate\u001b[90m: \u001b[39m\u001b[33m7\u001b[39m."
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2023-02-22T03:09:20.397Z",
"end_time": "2023-02-22T12:09:18.693000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "function incdecSubseqCnt_rev3(ary)\n incpairs = [(ary[begin], 1)]\n decpairs = [(ary[begin], 1)]\n for a in ary[begin+1:end]\n maxl = 1\n for (b, len) in incpairs\n if a > b && len > maxl - 1\n maxl = len + 1\n end\n end\n push!(incpairs, (a, maxl))\n maxl = 1\n for (b, len) in decpairs\n if a < b && len > maxl - 1\n maxl = len + 1\n end\n end\n push!(decpairs, (a, maxl))\n end\n incmaxl = maximum(len for (_a, len) in incpairs)\n decmaxl = maximum(len for (_a, len) in decpairs)\n return max(incmaxl, decmaxl)\nend",
"execution_count": 18,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 18,
"data": {
"text/plain": "incdecSubseqCnt_rev3 (generic function with 1 method)"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2023-02-22T03:09:20.966Z",
"end_time": "2023-02-22T12:09:21.501000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "@time for n = 3:10\n seq = 1:n\n ps = permutations(seq)\n cntlst=zeros(Int, n) \n for p = ps\n j = incdecSubseqCnt_rev3(p)\n cntlst[j] += 1\n end\n println(n,\" : \",cntlst)\nend",
"execution_count": 19,
"outputs": [
{
"output_type": "stream",
"text": "3 : [0, 4, 2]\n4 : [0, 4, 18, 2]\n5 : [0, 0, 86, 32, 2]\n6 : [0, 0, 306, 362, 50, 2]\n7 : [0, 0, 882, 3242, 842, 72, 2]\n8 : [0, 0, 1764, 24564, 12210, 1682, 98, 2]\n9 : [0, 0, 1764, 163872, 161158, 32930, 3026, 128, 2]\n10 : [0, 0, 0, 985032, 1969348, 592652, 76562, 5042, 162, 2]\n 2.164864 seconds (40.29 M allocations: 8.353 GiB, 12.36% gc time)\n",
"name": "stdout"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2023-02-22T03:09:25.021Z",
"end_time": "2023-02-22T12:09:24.919000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "Random.seed!(1234)\n@benchmark incdecSubseqCnt_rev3(p) setup=(p=Random.shuffle(1:10))",
"execution_count": 20,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 20,
"data": {
"text/plain": "BenchmarkTools.Trial: 10000 samples with 257 evaluations.\n Range \u001b[90m(\u001b[39m\u001b[36m\u001b[1mmin\u001b[22m\u001b[39m … \u001b[35mmax\u001b[39m\u001b[90m): \u001b[39m\u001b[36m\u001b[1m299.039 ns\u001b[22m\u001b[39m … \u001b[35m 4.539 μs\u001b[39m \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmin … max\u001b[90m): \u001b[39m0.00% … 83.42%\n Time \u001b[90m(\u001b[39m\u001b[34m\u001b[1mmedian\u001b[22m\u001b[39m\u001b[90m): \u001b[39m\u001b[34m\u001b[1m311.560 ns \u001b[22m\u001b[39m\u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmedian\u001b[90m): \u001b[39m0.00%\n Time \u001b[90m(\u001b[39m\u001b[32m\u001b[1mmean\u001b[22m\u001b[39m ± \u001b[32mσ\u001b[39m\u001b[90m): \u001b[39m\u001b[32m\u001b[1m348.699 ns\u001b[22m\u001b[39m ± \u001b[32m301.499 ns\u001b[39m \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmean ± σ\u001b[90m): \u001b[39m8.76% ± 9.16%\n\n \u001b[34m█\u001b[39m\u001b[32m \u001b[39m\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m▁\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m▁\n \u001b[34m█\u001b[39m\u001b[32m█\u001b[39m\u001b[39m▇\u001b[39m█\u001b[39m▆\u001b[39m▅\u001b[39m▄\u001b[39m▁\u001b[39m▃\u001b[39m▅\u001b[39m█\u001b[39m▄\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▃\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▅\u001b[39m \u001b[39m█\n 299 ns\u001b[90m \u001b[39m\u001b[90mHistogram: \u001b[39m\u001b[90m\u001b[1mlog(\u001b[22m\u001b[39m\u001b[90mfrequency\u001b[39m\u001b[90m\u001b[1m)\u001b[22m\u001b[39m\u001b[90m by time\u001b[39m 3.1 μs \u001b[0m\u001b[1m<\u001b[22m\n\n Memory estimate\u001b[90m: \u001b[39m\u001b[33m1.88 KiB\u001b[39m, allocs estimate\u001b[90m: \u001b[39m\u001b[33m7\u001b[39m."
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2023-02-22T03:33:05.488Z",
"end_time": "2023-02-22T12:33:03.743000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "function incdecSubseqCnt_rev4(ary)\n incpairs = [(ary[begin], 1)]\n decpairs = [(ary[begin], 1)]\n for a in ary[begin+1:end]\n push!(incpairs, (a, maximum(len for (b, len) in incpairs if a > b; init=0) + 1))\n push!(decpairs, (a, maximum(len for (b, len) in decpairs if a < b; init=0) + 1))\n end\n incmaxl = maximum(len for (_a, len) in incpairs)\n decmaxl = maximum(len for (_a, len) in decpairs)\n return max(incmaxl, decmaxl)\nend",
"execution_count": 27,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 27,
"data": {
"text/plain": "incdecSubseqCnt_rev4 (generic function with 1 method)"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2023-02-22T03:33:05.907Z",
"end_time": "2023-02-22T12:33:06.428000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "@time for n = 3:10\n seq = 1:n\n ps = permutations(seq)\n cntlst=zeros(Int, n) \n for p = ps\n j = incdecSubseqCnt_rev4(p)\n cntlst[j] += 1\n end\n println(n,\" : \",cntlst)\nend",
"execution_count": 28,
"outputs": [
{
"output_type": "stream",
"text": "3 : [0, 4, 2]\n4 : [0, 4, 18, 2]\n5 : [0, 0, 86, 32, 2]\n6 : [0, 0, 306, 362, 50, 2]\n7 : [0, 0, 882, 3242, 842, 72, 2]\n8 : [0, 0, 1764, 24564, 12210, 1682, 98, 2]\n9 : [0, 0, 1764, 163872, 161158, 32930, 3026, 128, 2]\n10 : [0, 0, 0, 985032, 1969348, 592652, 76562, 5042, 162, 2]\n 2.161857 seconds (40.29 M allocations: 8.353 GiB, 13.29% gc time)\n",
"name": "stdout"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2023-02-22T03:33:09.249Z",
"end_time": "2023-02-22T12:33:09.174000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "Random.seed!(1234)\n@benchmark incdecSubseqCnt_rev4(p) setup=(p=Random.shuffle(1:10))",
"execution_count": 29,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 29,
"data": {
"text/plain": "BenchmarkTools.Trial: 10000 samples with 283 evaluations.\n Range \u001b[90m(\u001b[39m\u001b[36m\u001b[1mmin\u001b[22m\u001b[39m … \u001b[35mmax\u001b[39m\u001b[90m): \u001b[39m\u001b[36m\u001b[1m282.343 ns\u001b[22m\u001b[39m … \u001b[35m 4.330 μs\u001b[39m \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmin … max\u001b[90m): \u001b[39m0.00% … 91.86%\n Time \u001b[90m(\u001b[39m\u001b[34m\u001b[1mmedian\u001b[22m\u001b[39m\u001b[90m): \u001b[39m\u001b[34m\u001b[1m300.203 ns \u001b[22m\u001b[39m\u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmedian\u001b[90m): \u001b[39m0.00%\n Time \u001b[90m(\u001b[39m\u001b[32m\u001b[1mmean\u001b[22m\u001b[39m ± \u001b[32mσ\u001b[39m\u001b[90m): \u001b[39m\u001b[32m\u001b[1m339.367 ns\u001b[22m\u001b[39m ± \u001b[32m307.747 ns\u001b[39m \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmean ± σ\u001b[90m): \u001b[39m9.66% ± 9.64%\n\n \u001b[34m█\u001b[39m\u001b[32m \u001b[39m\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m▁\n \u001b[34m█\u001b[39m\u001b[32m█\u001b[39m\u001b[39m█\u001b[39m█\u001b[39m▆\u001b[39m▅\u001b[39m▅\u001b[39m▄\u001b[39m▃\u001b[39m▅\u001b[39m█\u001b[39m▇\u001b[39m▃\u001b[39m▄\u001b[39m▁\u001b[39m▁\u001b[39m▃\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▃\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▄\u001b[39m▆\u001b[39m \u001b[39m█\n 282 ns\u001b[90m \u001b[39m\u001b[90mHistogram: \u001b[39m\u001b[90m\u001b[1mlog(\u001b[22m\u001b[39m\u001b[90mfrequency\u001b[39m\u001b[90m\u001b[1m)\u001b[22m\u001b[39m\u001b[90m by time\u001b[39m 2.98 μs \u001b[0m\u001b[1m<\u001b[22m\n\n Memory estimate\u001b[90m: \u001b[39m\u001b[33m1.88 KiB\u001b[39m, allocs estimate\u001b[90m: \u001b[39m\u001b[33m7\u001b[39m."
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2023-02-22T03:38:27.438Z",
"end_time": "2023-02-22T12:38:25.741000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "function incdecSubseqCnt_rev5(ary::AbstractArray{T}) where T\n incpairs = sizehint!(Tuple{T, Int}[], length(ary))\n decpairs = sizehint!(Tuple{T, Int}[], length(ary))\n for a in ary\n push!(incpairs, (a, maximum(len for (b, len) in incpairs if a > b; init=0) + 1))\n push!(decpairs, (a, maximum(len for (b, len) in decpairs if a < b; init=0) + 1))\n end\n incmaxl = maximum(len for (_a, len) in incpairs)\n decmaxl = maximum(len for (_a, len) in decpairs)\n return max(incmaxl, decmaxl)\nend",
"execution_count": 30,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 30,
"data": {
"text/plain": "incdecSubseqCnt_rev5 (generic function with 1 method)"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2023-02-22T03:38:29.703Z",
"end_time": "2023-02-22T12:38:30.290000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "@time for n = 3:10\n seq = 1:n\n ps = permutations(seq)\n cntlst=zeros(Int, n) \n for p = ps\n j = incdecSubseqCnt_rev5(p)\n cntlst[j] += 1\n end\n println(n,\" : \",cntlst)\nend",
"execution_count": 31,
"outputs": [
{
"output_type": "stream",
"text": "3 : [0, 4, 2]\n4 : [0, 4, 18, 2]\n5 : [0, 0, 86, 32, 2]\n6 : [0, 0, 306, 362, 50, 2]\n7 : [0, 0, 882, 3242, 842, 72, 2]\n8 : [0, 0, 1764, 24564, 12210, 1682, 98, 2]\n9 : [0, 0, 1764, 163872, 161158, 32930, 3026, 128, 2]\n10 : [0, 0, 0, 985032, 1969348, 592652, 76562, 5042, 162, 2]\n 2.241997 seconds (28.27 M allocations: 2.983 GiB, 14.49% gc time)\n",
"name": "stdout"
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2023-02-22T03:38:33.139Z",
"end_time": "2023-02-22T12:38:33.152000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "Random.seed!(1234)\n@benchmark incdecSubseqCnt_rev5(p) setup=(p=Random.shuffle(1:10))",
"execution_count": 32,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 32,
"data": {
"text/plain": "BenchmarkTools.Trial: 10000 samples with 417 evaluations.\n Range \u001b[90m(\u001b[39m\u001b[36m\u001b[1mmin\u001b[22m\u001b[39m … \u001b[35mmax\u001b[39m\u001b[90m): \u001b[39m\u001b[36m\u001b[1m236.086 ns\u001b[22m\u001b[39m … \u001b[35m 4.222 μs\u001b[39m \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmin … max\u001b[90m): \u001b[39m0.00% … 92.17%\n Time \u001b[90m(\u001b[39m\u001b[34m\u001b[1mmedian\u001b[22m\u001b[39m\u001b[90m): \u001b[39m\u001b[34m\u001b[1m244.347 ns \u001b[22m\u001b[39m\u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmedian\u001b[90m): \u001b[39m0.00%\n Time \u001b[90m(\u001b[39m\u001b[32m\u001b[1mmean\u001b[22m\u001b[39m ± \u001b[32mσ\u001b[39m\u001b[90m): \u001b[39m\u001b[32m\u001b[1m261.615 ns\u001b[22m\u001b[39m ± \u001b[32m209.994 ns\u001b[39m \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmean ± σ\u001b[90m): \u001b[39m5.14% ± 5.96%\n\n \u001b[39m \u001b[39m \u001b[39m█\u001b[39m█\u001b[34m▆\u001b[39m\u001b[39m▆\u001b[39m▃\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[32m \u001b[39m\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \n \u001b[39m▂\u001b[39m▇\u001b[39m█\u001b[39m█\u001b[34m█\u001b[39m\u001b[39m█\u001b[39m█\u001b[39m▆\u001b[39m▃\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▁\u001b[32m▁\u001b[39m\u001b[39m▂\u001b[39m▁\u001b[39m▁\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▁\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▁\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m \u001b[39m▃\n 236 ns\u001b[90m Histogram: frequency by time\u001b[39m 351 ns \u001b[0m\u001b[1m<\u001b[22m\n\n Memory estimate\u001b[90m: \u001b[39m\u001b[33m480 bytes\u001b[39m, allocs estimate\u001b[90m: \u001b[39m\u001b[33m4\u001b[39m."
},
"metadata": {}
}
]
},
{
"metadata": {
"trusted": true
},
"cell_type": "code",
"source": "",
"execution_count": null,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2023-02-22T03:39:48.810Z",
"end_time": "2023-02-22T12:39:49.170000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "Random.seed!(1234)\n@benchmark incdecSubseqCnt_rev1(p) setup=(p=Random.shuffle(1:10))",
"execution_count": 33,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 33,
"data": {
"text/plain": "BenchmarkTools.Trial: 10000 samples with 132 evaluations.\n Range \u001b[90m(\u001b[39m\u001b[36m\u001b[1mmin\u001b[22m\u001b[39m … \u001b[35mmax\u001b[39m\u001b[90m): \u001b[39m\u001b[36m\u001b[1m718.917 ns\u001b[22m\u001b[39m … \u001b[35m18.322 μs\u001b[39m \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmin … max\u001b[90m): \u001b[39m 0.00% … 93.30%\n Time \u001b[90m(\u001b[39m\u001b[34m\u001b[1mmedian\u001b[22m\u001b[39m\u001b[90m): \u001b[39m\u001b[34m\u001b[1m754.277 ns \u001b[22m\u001b[39m\u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmedian\u001b[90m): \u001b[39m 0.00%\n Time \u001b[90m(\u001b[39m\u001b[32m\u001b[1mmean\u001b[22m\u001b[39m ± \u001b[32mσ\u001b[39m\u001b[90m): \u001b[39m\u001b[32m\u001b[1m871.889 ns\u001b[22m\u001b[39m ± \u001b[32m 1.263 μs\u001b[39m \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmean ± σ\u001b[90m): \u001b[39m12.32% ± 8.04%\n\n \u001b[39m \u001b[39m▁\u001b[39m█\u001b[34m█\u001b[39m\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[32m \u001b[39m\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \n \u001b[39m▃\u001b[39m█\u001b[39m█\u001b[34m█\u001b[39m\u001b[39m█\u001b[39m▅\u001b[39m▃\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[32m▂\u001b[39m\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▁\u001b[39m▂\u001b[39m▁\u001b[39m▁\u001b[39m▂\u001b[39m▁\u001b[39m▂\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▁\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▁\u001b[39m▂\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m \u001b[39m▂\n 719 ns\u001b[90m Histogram: frequency by time\u001b[39m 1.4 μs \u001b[0m\u001b[1m<\u001b[22m\n\n Memory estimate\u001b[90m: \u001b[39m\u001b[33m2.50 KiB\u001b[39m, allocs estimate\u001b[90m: \u001b[39m\u001b[33m26\u001b[39m."
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2023-02-22T03:39:48.817Z",
"end_time": "2023-02-22T12:39:55.894000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "Random.seed!(1234)\n@benchmark incdecSubseqCnt_rev2(p) setup=(p=Random.shuffle(1:10))",
"execution_count": 34,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 34,
"data": {
"text/plain": "BenchmarkTools.Trial: 10000 samples with 239 evaluations.\n Range \u001b[90m(\u001b[39m\u001b[36m\u001b[1mmin\u001b[22m\u001b[39m … \u001b[35mmax\u001b[39m\u001b[90m): \u001b[39m\u001b[36m\u001b[1m313.632 ns\u001b[22m\u001b[39m … \u001b[35m 5.496 μs\u001b[39m \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmin … max\u001b[90m): \u001b[39m0.00% … 85.59%\n Time \u001b[90m(\u001b[39m\u001b[34m\u001b[1mmedian\u001b[22m\u001b[39m\u001b[90m): \u001b[39m\u001b[34m\u001b[1m329.255 ns \u001b[22m\u001b[39m\u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmedian\u001b[90m): \u001b[39m0.00%\n Time \u001b[90m(\u001b[39m\u001b[32m\u001b[1mmean\u001b[22m\u001b[39m ± \u001b[32mσ\u001b[39m\u001b[90m): \u001b[39m\u001b[32m\u001b[1m369.478 ns\u001b[22m\u001b[39m ± \u001b[32m340.239 ns\u001b[39m \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmean ± σ\u001b[90m): \u001b[39m8.97% ± 8.90%\n\n \u001b[39m▅\u001b[34m█\u001b[39m\u001b[39m▅\u001b[39m \u001b[39m \u001b[32m \u001b[39m\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m▁\n \u001b[39m█\u001b[34m█\u001b[39m\u001b[39m█\u001b[39m█\u001b[39m▆\u001b[32m▅\u001b[39m\u001b[39m▇\u001b[39m▇\u001b[39m▆\u001b[39m▇\u001b[39m▅\u001b[39m▃\u001b[39m▅\u001b[39m▃\u001b[39m▆\u001b[39m▇\u001b[39m▅\u001b[39m▄\u001b[39m▄\u001b[39m▃\u001b[39m▄\u001b[39m▄\u001b[39m▃\u001b[39m▁\u001b[39m▄\u001b[39m▃\u001b[39m▃\u001b[39m▄\u001b[39m▃\u001b[39m▁\u001b[39m▃\u001b[39m▁\u001b[39m▃\u001b[39m▁\u001b[39m▃\u001b[39m▁\u001b[39m▃\u001b[39m▃\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▄\u001b[39m▄\u001b[39m▄\u001b[39m▆\u001b[39m▇\u001b[39m▇\u001b[39m▆\u001b[39m▄\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▃\u001b[39m▃\u001b[39m \u001b[39m█\n 314 ns\u001b[90m \u001b[39m\u001b[90mHistogram: \u001b[39m\u001b[90m\u001b[1mlog(\u001b[22m\u001b[39m\u001b[90mfrequency\u001b[39m\u001b[90m\u001b[1m)\u001b[22m\u001b[39m\u001b[90m by time\u001b[39m 959 ns \u001b[0m\u001b[1m<\u001b[22m\n\n Memory estimate\u001b[90m: \u001b[39m\u001b[33m1.88 KiB\u001b[39m, allocs estimate\u001b[90m: \u001b[39m\u001b[33m7\u001b[39m."
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2023-02-22T03:39:48.817Z",
"end_time": "2023-02-22T12:39:55.894000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "Random.seed!(1234)\n@benchmark incdecSubseqCnt_rev3(p) setup=(p=Random.shuffle(1:10))",
"execution_count": 35,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 35,
"data": {
"text/plain": "BenchmarkTools.Trial: 10000 samples with 259 evaluations.\n Range \u001b[90m(\u001b[39m\u001b[36m\u001b[1mmin\u001b[22m\u001b[39m … \u001b[35mmax\u001b[39m\u001b[90m): \u001b[39m\u001b[36m\u001b[1m302.347 ns\u001b[22m\u001b[39m … \u001b[35m 4.807 μs\u001b[39m \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmin … max\u001b[90m): \u001b[39m0.00% … 90.13%\n Time \u001b[90m(\u001b[39m\u001b[34m\u001b[1mmedian\u001b[22m\u001b[39m\u001b[90m): \u001b[39m\u001b[34m\u001b[1m317.454 ns \u001b[22m\u001b[39m\u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmedian\u001b[90m): \u001b[39m0.00%\n Time \u001b[90m(\u001b[39m\u001b[32m\u001b[1mmean\u001b[22m\u001b[39m ± \u001b[32mσ\u001b[39m\u001b[90m): \u001b[39m\u001b[32m\u001b[1m357.941 ns\u001b[22m\u001b[39m ± \u001b[32m338.550 ns\u001b[39m \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmean ± σ\u001b[90m): \u001b[39m9.68% ± 9.31%\n\n \u001b[34m█\u001b[39m\u001b[32m▁\u001b[39m\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m▁\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m▁\n \u001b[34m█\u001b[39m\u001b[32m█\u001b[39m\u001b[39m▇\u001b[39m▆\u001b[39m▄\u001b[39m▄\u001b[39m▄\u001b[39m▃\u001b[39m▅\u001b[39m█\u001b[39m▄\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▅\u001b[39m \u001b[39m█\n 302 ns\u001b[90m \u001b[39m\u001b[90mHistogram: \u001b[39m\u001b[90m\u001b[1mlog(\u001b[22m\u001b[39m\u001b[90mfrequency\u001b[39m\u001b[90m\u001b[1m)\u001b[22m\u001b[39m\u001b[90m by time\u001b[39m 3.44 μs \u001b[0m\u001b[1m<\u001b[22m\n\n Memory estimate\u001b[90m: \u001b[39m\u001b[33m1.88 KiB\u001b[39m, allocs estimate\u001b[90m: \u001b[39m\u001b[33m7\u001b[39m."
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2023-02-22T03:39:48.817Z",
"end_time": "2023-02-22T12:39:55.894000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "Random.seed!(1234)\n@benchmark incdecSubseqCnt_rev4(p) setup=(p=Random.shuffle(1:10))",
"execution_count": 36,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 36,
"data": {
"text/plain": "BenchmarkTools.Trial: 10000 samples with 285 evaluations.\n Range \u001b[90m(\u001b[39m\u001b[36m\u001b[1mmin\u001b[22m\u001b[39m … \u001b[35mmax\u001b[39m\u001b[90m): \u001b[39m\u001b[36m\u001b[1m282.796 ns\u001b[22m\u001b[39m … \u001b[35m 4.645 μs\u001b[39m \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmin … max\u001b[90m): \u001b[39m0.00% … 84.34%\n Time \u001b[90m(\u001b[39m\u001b[34m\u001b[1mmedian\u001b[22m\u001b[39m\u001b[90m): \u001b[39m\u001b[34m\u001b[1m299.754 ns \u001b[22m\u001b[39m\u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmedian\u001b[90m): \u001b[39m0.00%\n Time \u001b[90m(\u001b[39m\u001b[32m\u001b[1mmean\u001b[22m\u001b[39m ± \u001b[32mσ\u001b[39m\u001b[90m): \u001b[39m\u001b[32m\u001b[1m338.779 ns\u001b[22m\u001b[39m ± \u001b[32m311.593 ns\u001b[39m \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmean ± σ\u001b[90m): \u001b[39m9.84% ± 9.68%\n\n \u001b[34m█\u001b[39m\u001b[32m▁\u001b[39m\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m▁\n \u001b[34m█\u001b[39m\u001b[32m█\u001b[39m\u001b[39m▇\u001b[39m▇\u001b[39m▅\u001b[39m▅\u001b[39m▄\u001b[39m▄\u001b[39m▃\u001b[39m▄\u001b[39m█\u001b[39m▆\u001b[39m▄\u001b[39m▄\u001b[39m▄\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▇\u001b[39m \u001b[39m█\n 283 ns\u001b[90m \u001b[39m\u001b[90mHistogram: \u001b[39m\u001b[90m\u001b[1mlog(\u001b[22m\u001b[39m\u001b[90mfrequency\u001b[39m\u001b[90m\u001b[1m)\u001b[22m\u001b[39m\u001b[90m by time\u001b[39m 3.05 μs \u001b[0m\u001b[1m<\u001b[22m\n\n Memory estimate\u001b[90m: \u001b[39m\u001b[33m1.88 KiB\u001b[39m, allocs estimate\u001b[90m: \u001b[39m\u001b[33m7\u001b[39m."
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"start_time": "2023-02-22T03:39:48.817Z",
"end_time": "2023-02-22T12:39:55.894000+09:00"
},
"trusted": true
},
"cell_type": "code",
"source": "Random.seed!(1234)\n@benchmark incdecSubseqCnt_rev5(p) setup=(p=Random.shuffle(1:10))",
"execution_count": 37,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 37,
"data": {
"text/plain": "BenchmarkTools.Trial: 10000 samples with 417 evaluations.\n Range \u001b[90m(\u001b[39m\u001b[36m\u001b[1mmin\u001b[22m\u001b[39m … \u001b[35mmax\u001b[39m\u001b[90m): \u001b[39m\u001b[36m\u001b[1m236.446 ns\u001b[22m\u001b[39m … \u001b[35m 4.234 μs\u001b[39m \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmin … max\u001b[90m): \u001b[39m0.00% … 92.26%\n Time \u001b[90m(\u001b[39m\u001b[34m\u001b[1mmedian\u001b[22m\u001b[39m\u001b[90m): \u001b[39m\u001b[34m\u001b[1m244.518 ns \u001b[22m\u001b[39m\u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmedian\u001b[90m): \u001b[39m0.00%\n Time \u001b[90m(\u001b[39m\u001b[32m\u001b[1mmean\u001b[22m\u001b[39m ± \u001b[32mσ\u001b[39m\u001b[90m): \u001b[39m\u001b[32m\u001b[1m261.852 ns\u001b[22m\u001b[39m ± \u001b[32m210.280 ns\u001b[39m \u001b[90m┊\u001b[39m GC \u001b[90m(\u001b[39mmean ± σ\u001b[90m): \u001b[39m5.15% ± 5.96%\n\n \u001b[39m \u001b[39m▁\u001b[39m█\u001b[39m█\u001b[34m▇\u001b[39m\u001b[39m▇\u001b[39m▂\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[32m \u001b[39m\u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \u001b[39m \n \u001b[39m▃\u001b[39m█\u001b[39m█\u001b[39m█\u001b[34m█\u001b[39m\u001b[39m█\u001b[39m█\u001b[39m▅\u001b[39m▃\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[32m▂\u001b[39m\u001b[39m▂\u001b[39m▂\u001b[39m▁\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▁\u001b[39m▁\u001b[39m▁\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m▂\u001b[39m \u001b[39m▃\n 236 ns\u001b[90m Histogram: frequency by time\u001b[39m 352 ns \u001b[0m\u001b[1m<\u001b[22m\n\n Memory estimate\u001b[90m: \u001b[39m\u001b[33m480 bytes\u001b[39m, allocs estimate\u001b[90m: \u001b[39m\u001b[33m4\u001b[39m."
},
"metadata": {}
}
]
},
{
"metadata": {
"trusted": true
},
"cell_type": "code",
"source": "",
"execution_count": null,
"outputs": []
}
],
"metadata": {
"kernelspec": {
"name": "julia-_4-threads_-1.8",
"display_name": "Julia (4 threads) 1.8.5",
"language": "julia"
},
"language_info": {
"file_extension": ".jl",
"name": "julia",
"mimetype": "application/julia",
"version": "1.8.5"
},
"gist": {
"id": "",
"data": {
"description": "20230220CntLenIncDecSub.by.Sb2.ipynb",
"public": true
}
}
},
"nbformat": 4,
"nbformat_minor": 5
}
Raw
Project.toml
[compat]
julia = "1.6"
[deps]
BenchmarkTools = "6e4b80f9-dd63-53aa-95a3-0cdb28fa8baf"
Combinatorics = "861a8166-3701-5b0c-9a16-15d98fcdc6aa"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment