Person re-identification is a recently introduced computer vision task that consists of recognising an individual who was previously observed over a video-surveillance camera network. Among the open problems, in this paper we focus on computational complexity. Despite its practical relevance, especially in real-time applications, this issue has been overlooked in the literature so far. In this paper, we address it by exploiting a framework we proposed in a previous work. It allows us to turn any person re-identification method, that uses multiple components and a body part subdivision model, into a dissimilarity-based one. Each individual is represented as a vector of dissimilarity values to a set of visual prototypes, that are drawn from the original non-dissimilarity representation. Experiments on two benchmark datasets provide evidence that a dissimilarity representation provides very fast re-identification methods. We also show that, even if the re-identification accuracy can be lower (especially when the number of candidates is low), the trade-off between processing time and accuracy can nevertheless be advantageous, in real-time application scenarios involving a human operator.