applicability-prereqs   22

data structures - Why are Red-Black trees so popular? - Computer Science Stack Exchange
- AVL trees have smaller average depth than red-black trees, and thus searching for a value in AVL tree is consistently faster.
- Red-black trees make less structural changes to balance themselves than AVL trees, which could make them potentially faster for insert/delete. I'm saying potentially, because this would depend on the cost of the structural change to the tree, as this will depend a lot on the runtime and implemntation (might also be completely different in a functional language when the tree is immutable?)

There are many benchmarks online that compare AVL and Red-black trees, but what struck me is that my professor basically said, that usually you'd do one of two things:
- Either you don't really care that much about performance, in which case the 10-20% difference of AVL vs Red-black in most cases won't matter at all.
- Or you really care about performance, in which you case you'd ditch both AVL and Red-black trees, and go with B-trees, which can be tweaked to work much better (or (a,b)-trees, I'm gonna put all of those in one basket.)


> For some kinds of binary search trees, including red-black trees but not AVL trees, the "fixes" to the tree can fairly easily be predicted on the way down and performed during a single top-down pass, making the second pass unnecessary. Such insertion algorithms are typically implemented with a loop rather than recursion, and often run slightly faster in practice than their two-pass counterparts.

So a RedBlack tree insert can be implemented without recursion, on some CPUs recursion is very expensive if you overrun the function call cache (e.g SPARC due to is use of Register window)


There are some cases where you can't use B-trees at all.

One prominent case is std::map from C++ STL. The standard requires that insert does not invalidate existing iterators


I also believe that "single pass tail recursive" implementation is not the reason for red black tree popularity as a mutable data structure.

First of all, stack depth is irrelevant here, because (given log𝑛 height) you would run out of the main memory before you run out of stack space. Jemalloc is happy with preallocating worst case depth on the stack.
nibble  q-n-a  overflow  cs  algorithms  tcs  data-structures  functional  orders  trees  cost-benefit  tradeoffs  roots  explanans  impetus  performance  applicability-prereqs  programming  pls  c(pp) 
yesterday by nhaliday
algorithm - Skip List vs. Binary Search Tree - Stack Overflow
Skip lists are more amenable to concurrent access/modification. Herb Sutter wrote an article about data structure in concurrent environments. It has more indepth information.

The most frequently used implementation of a binary search tree is a red-black tree. The concurrent problems come in when the tree is modified it often needs to rebalance. The rebalance operation can affect large portions of the tree, which would require a mutex lock on many of the tree nodes. Inserting a node into a skip list is far more localized, only nodes directly linked to the affected node need to be locked.
q-n-a  stackex  nibble  programming  tcs  data-structures  performance  concurrency  comparison  cost-benefit  applicability-prereqs  random  trees 
5 weeks ago by nhaliday
its-not-software - steveyegge2
You don't work in the software industry.


So what's the software industry, and how do we differ from it?

Well, the software industry is what you learn about in school, and it's what you probably did at your previous company. The software industry produces software that runs on customers' machines β€” that is, software intended to run on a machine over which you have no control.

So it includes pretty much everything that Microsoft does: Windows and every application you download for it, including your browser.

It also includes everything that runs in the browser, including Flash applications, Java applets, and plug-ins like Adobe's Acrobat Reader. Their deployment model is a little different from the "classic" deployment models, but it's still software that you package up and release to some unknown client box.



Our industry is so different from the software industry, and it's so important to draw a clear distinction, that it needs a new name. I'll call it Servware for now, lacking anything better. Hardware, firmware, software, servware. It fits well enough.

Servware is stuff that lives on your own servers. I call it "stuff" advisedly, since it's more than just software; it includes configuration, monitoring systems, data, documentation, and everything else you've got there, all acting in concert to produce some observable user experience on the other side of a network connection.
techtariat  sv  tech  rhetoric  essay  software  saas  devops  engineering  programming  contrarianism  list  top-n  best-practices  applicability-prereqs  desktop  flux-stasis  homo-hetero  trends  games  thinking  checklists  dbs  models  communication  tutorial  wiki  integration-extension  frameworks  api  whole-partial-many  metrics  retrofit  c(pp)  pls  code-dive  planning  working-stiff  composition-decomposition  libraries  conceptual-vocab  amazon  system-design 
6 weeks ago by nhaliday
All models are wrong - Wikipedia
Box repeated the aphorism in a paper that was published in the proceedings of a 1978 statistics workshop.[2] The paper contains a section entitled "All models are wrong but some are useful". The section is copied below.

Now it would be very remarkable if any system existing in the real world could be exactly represented by any simple model. However, cunningly chosen parsimonious models often do provide remarkably useful approximations. For example, the law PV = RT relating pressure P, volume V and temperature T of an "ideal" gas via a constant R is not exactly true for any real gas, but it frequently provides a useful approximation and furthermore its structure is informative since it springs from a physical view of the behavior of gas molecules.

For such a model there is no need to ask the question "Is the model true?". If "truth" is to be the "whole truth" the answer must be "No". The only question of interest is "Is the model illuminating and useful?".
thinking  metabuch  metameta  map-territory  models  accuracy  wire-guided  truth  philosophy  stats  data-science  methodology  lens  wiki  reference  complex-systems  occam  parsimony  science  nibble  hi-order-bits  info-dynamics  the-trenches  meta:science  physics  fluid  thermo  stat-mech  applicability-prereqs  theory-practice  elegance 
august 2017 by nhaliday
How Universal Is the Big Five? Testing the Five-Factor Model of Personality Variation Among Forager–Farmers in the Bolivian Amazon
We failed to find robust support for the FFM, based on tests of (a) internal consistency of items expected to segregate into the Big Five factors, (b) response stability of the Big Five, (c) external validity of the Big Five with respect to observed behavior, (d) factor structure according to exploratory and confirmatory factor analysis, and (e) similarity with a U.S. target structure based on Procrustes rotation analysis.


We argue that Tsimane personality variation displays 2 principal factors that may reflect socioecological characteristics common to small-scale societies. We offer evolutionary perspectives on why the structure of personality variation may not be invariant across human societies.
pdf  study  psychology  cog-psych  society  embedded-cognition  personality  metrics  generalization  methodology  farmers-and-foragers  latin-america  context  homo-hetero  info-dynamics  water  psychometrics  exploratory  things  phalanges  dimensionality  anthropology  universalism-particularism  applicability-prereqs 
february 2017 by nhaliday
Programming books you might want to consider reading
- surprisingly theory-focused actually (w/ a smattering of OS/systems and hardware)
- cites among others: DPV, CLRS, Okasaki, Erik Demaine
- a bunch of AGT stuff
- some SWE stuff
- some business/tech culture stuff
- math (calc and prob.)
- he mentions Jukna's Extremal Combinatorics in passing at the end, wow
advice  dan-luu  engineering  books  list  recommendations  reading  accretion  πŸ–₯  2016  top-n  info-foraging  techtariat  confluence  p:null  quixotic  advanced  pragmatic  applications  applicability-prereqs  working-stiff  career  jobs  recruiting  algorithms  tcs  data-structures  functional  performance  time-complexity  random  rand-approx  complexity  cs  computation  learning-theory  machine-learning  acm  os  systems  linux  unix  concurrency  s:***  programming  nitty-gritty  problem-solving  hardware  algorithmic-econ  game-theory  mechanism-design  IEEE  erik-demaine  ground-up  legacy  code-dive  system-design  best-practices  business  microsoft  competition  culture  dark-arts  management  tech  twitter  sv  productivity  aging  art-generation  art  math  probability  math.CO  math.CA  electromag  p:someday 
october 2016 by nhaliday

related tags

2016  accretion  accuracy  acm  acmtariat  advanced  adversarial  advice  aging  ai  algorithmic-econ  algorithms  amazon  analytical-holistic  anthropology  api  applications  art-generation  art  article  behavioral-econ  behavioral-gen  being-right  best-practices  biodet  bitcoin  blockchain  bonferroni  books  brands  business  c(pp)  caching  career  chapman  charity  cheatsheet  checklists  chemistry  clever-rats  code-dive  cog-psych  commentary  communication  communism  comparison  competition  complex-systems  complexity  composition-decomposition  computation  concentration-of-measure  concept  conceptual-vocab  concurrency  confluence  context  contradiction  contrarianism  convergence  cooperate-defect  cost-benefit  counterexample  critique  crosstab  crux  cryptocurrency  cs  culture  curiosity  dan-luu  dark-arts  data-science  data-structures  data  dbs  debate  decision-making  decision-theory  dennett  density  dependence-independence  descriptive  desktop  devops  dimensionality  dirty-hands  discussion  duality  economics  electromag  elegance  embedded-cognition  empirical  engineering  epistemic  erik-demaine  essay  examples  expert-experience  expert  explanans  explanation  exploratory  exposition  farmers-and-foragers  fertility  finance  fluid  flux-stasis  fourier  frameworks  frontier  functional  futurism  game-theory  games  gcta  generalization  genetics  genomics  gravity  ground-up  gt-101  hardware  heuristic  hi-order-bits  homo-hetero  howto  hsu  humility  identity  ieee  iidness  impetus  inference  info-dynamics  info-foraging  init  insight  integration-extension  integrity  interview  intuition  is-ought  jargon  jobs  latin-america  learning-theory  legacy  lens  lesswrong  levers  libraries  limits  links  linux  list  local-global  logic  machine-learning  magnitude  management  map-territory  math  measure  measurement  mechanics  mechanism-design  meta:prediction  meta:rhetoric  meta:science  metabuch  metameta  methodology  metrics  micro  microfoundations  microsoft  minimum-viable  miri-cfar  models  motivation  multiplicative  neurons  nibble  nitty-gritty  objektbuch  occam  orders  org:edu  org:junk  os  overflow  p:null  p:someday  parsimony  pdf  performance  personality  phalanges  philosophy  physics  pic  planning  pls  postrat  pragmatic  priors-posteriors  probability  problem-solving  productivity  programming  properties  psychology  psychometrics  q-n-a  quantum  quixotic  rand-approx  random  rant  rationality  ratty  reading  realness  reason  recommendations  recruiting  reduction  reference  reflection  reinforcement  relativity  replication  retrofit  rhetoric  risk  robust  roots  russia  rust  s:***  saas  sampling-bias  scale  science  scitariat  search  simulation  skeleton  social-science  society  software  space  spearhead  speed  speedometer  stackex  stat-mech  state  stats  stories  strategy  strings  structure  study  subculture  summary  sv  synthesis  system-design  systematic-ad-hoc  systems  tcs  tech  techtariat  telos-atelos  temperature  terminal  tetlock  the-trenches  theory-practice  thermo  thick-thin  things  thinking  time-complexity  top-n  tradeoffs  trees  trends  tricki  trust  truth  tutorial  twin-study  twitter  universalism-particularism  unix  vague  values  water  west-hunter  whole-partial-many  wiki  wire-guided  working-stiff  wormholes  yak-shaving  yoga  zooming  🎩  πŸ”¬  πŸ–₯  πŸ¦€ 

Copy this bookmark: