data structures - Stack - scala implementation/performance issue -


i've been looking @ scala-lang notes on various data structures , performance characteristics.

i have noticed immutable.stack has c (const.) complexity both appending , prepending, while mutable.stack stack has c complexity prepending , l (linear) complexity appending. surprised me bit.

i take it, "appending" means push() top of stack. , since complexities prepending , appending different, mean "prepending" in fact putting on bottom of stack? why perform better (c mutable) appending (l mutable)? , also, how can prepend stack? can't see method suitable in scaladoc.

edit.

as @Łukasz noted in comments, can prepend , append stack +: , :+ operators. question remains though - why prepending work better (faster) appending stack? should add bottom instead of pushing top?

it looks there mistake in table, or not something. if @ implementation, push both mutable , immutable stack takes constant time, , :+ both mutable , immutable takes linear time, because :+ coming seqlike in linear time, reasonable stack data structure

both mutable , immutable stacks using immutable list inside , using :: operation, constant. list has it's append operation l, it's no way stack can better

for immutable stack is:

def push[b >: a](elem: b): stack[b] = new stack(elem :: elems)

and mutable is:

def push(elem: a): this.type = { elems = elem :: elems; }

also please notice immutable stack deprecated since 2.11

p.s. checked latest sources of 2.12, seems code didn't change since 2.11

p.p.s. couldn't find insert implementation stack, , looking @ table seems weird stack among immutable structures can insert data, i'd guess l column should have been in append column


Comments

Post a Comment

Popular posts from this blog

php - Wordpress website dashboard page or post editor content is not showing but front end data is showing properly -

Image
recently have uploaded wordpress site onto server. have uploaded wordpress site in sub-folder under root folder ../root(domain root folder)/wordpress (where host wordpress folder). now problem content data in page or post in dashboard of wordpress admin panel not showing - see image. but data showing in front view - see image. if not browser cache issue , not issue happened tinymce editor during upgrade; try add config file: define('concatenate_scripts', false);
Read more

How to get the ip address of VM and use it to configure SSH connection dynamically in Ansible -

i trying ip address of vm , trying use establish ssh vm. following script: --- - hosts: localhost become: yes connection: local gather_facts: false serial: 1 vars_files: - createvmvars.yml tasks: - name: gathering vm info. vsphere_guest: vcenter_hostname: "{{vcenter_hostname}}" username: "{{vcenter_username}}" password: "{{vcenter_password}}" guest: "{{guest_name}}" vmware_guest_facts: yes register: var - debug: msg="{{var.ansible_facts.hw_eth0.ipaddresses[0]}}" - name: establishing ssh connection. script: /home/shasha/devops/scripts/ssh_configure.sh "{{var.ansible_facts.hw_eth0.ipaddresses[0]}}" following content of ssh_configure.sh : #!/bin/sh ssh-keygen -t rsa ssh-copy-id $1 but when running playbook, getting following error while executing third task: error! 'var' undefined but debug module(second task) printin
Read more

javascript - Get parameter of GET request -

i make request: createxhrrequest( "get", fileurl, function( err, response ) { if( err ) { alert( "error get!" ); } alert(response); }); and full response: { "status" : "ok", "message" : "jvberi0xljqkjdduxdgkmy how can jvberi0xlj ? i try response.message , response["message"]. nothing works. just simple access this: var json = json.parse(response); json.message
Read more